Find Index Pairs of Matching Elements in Arrays

Scenario

Marketing analytics team needs to find common elements between two sorted arrays of user IDs.

Question

Given two sorted integer arrays without duplicates, return the list of index pairs where the elements match, e.g., arr1=[1,4,5,6,7,9], arr2=[1,2,3,6,9] -> [[0,0],[3,3],[5,4]].

Follow-ups:

Discuss possible edge cases.

If the arrays can contain duplicates (arr1=[1,1,4,5,6,6,6,7,9], arr2=[1,2,3,6,6,9,9]), modify your algorithm to return all valid index pairs.

Hints

Think two-pointer merge approach; handle duplicates with nested loops; analyze O(n+m) time.

Find Index Pairs of Matching Elements in Sorted Arrays

Given two sorted integer arrays arr1 and arr2 that each contain no duplicate values, return the list of index pairs [i, j] such that arr1[i] == arr2[j].

Return the pairs ordered by i (which, because both arrays are sorted and duplicate-free, also makes them ordered by j).

Example: arr1 = [1,4,5,6,7,9], arr2 = [1,2,3,6,9] -> [[0,0],[3,3],[5,4]] (value 1 at indices 0/0, value 6 at indices 3/3, value 9 at indices 5/4).

Use a two-pointer merge for O(n + m) time.

Constraints

• Both arrays are sorted in non-decreasing order.
• Within each array all values are distinct (no duplicates).
• Either array may be empty.
• Values may be negative.

Hints

1. Walk both arrays with two pointers i and j, advancing the pointer at the smaller value.
2. When arr1[i] == arr2[j], record [i, j] and advance BOTH pointers.
3. Because there are no duplicates, you never need to look back — the merge is strictly O(n + m).

Index Pairs of Matching Elements With Duplicates

Follow-up: now the two sorted arrays MAY contain duplicate values. Return every valid index pair [i, j] where arr1[i] == arr2[j].

For a value that appears multiple times, each occurrence index in arr1 must be paired with each occurrence index in arr2 (the Cartesian product of the two index groups).

Return pairs ordered by i, then by j.

Example: arr1 = [1,1,4,5,6,6,6,7,9], arr2 = [1,2,3,6,6,9,9] -> value 1 (arr1 idx 0,1 x arr2 idx 0) gives [0,0],[1,0]; value 6 (arr1 idx 4,5,6 x arr2 idx 3,4) gives the 6 combinations; value 9 (arr1 idx 8 x arr2 idx 5,6) gives [8,5],[8,6].

Keep it O(n + m + k) where k is the number of output pairs by grouping equal runs.

Constraints

• Both arrays are sorted in non-decreasing order.
• Arrays may contain duplicate values.
• Either array may be empty.
• Values may be negative.
• Output may be large (up to the product of the run lengths for a shared value).

Hints

1. Still merge with two pointers, but when the values are equal, find the FULL run of that value in each array.
2. Emit the Cartesian product of the arr1 index run and the arr2 index run, then advance both pointers past their runs.
3. Iterating the arr1 run in the outer loop and arr2 run in the inner loop yields pairs already sorted by (i, j).