How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Walmart Labs.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Walmart Labs during technical interviews.

Find Index Pairs of Matching Elements in Arrays

Company: Walmart Labs

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### 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.

Quick Answer: This question evaluates the ability to work with sorted arrays, index mapping, duplicate handling, and reasoning about correctness and algorithmic complexity.

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.

Examples

Input: ([1,4,5,6,7,9], [1,2,3,6,9])

Expected Output: [[0, 0], [3, 3], [5, 4]]

Explanation: Matches at value 1 (0,0), value 6 (3,3), value 9 (5,4).

Input: ([], [1,2,3])

Expected Output: []

Explanation: First array empty -> no pairs.

Input: ([1,2,3], [])

Expected Output: []

Explanation: Second array empty -> no pairs.

Input: ([1,2,3], [4,5,6])

Expected Output: []

Explanation: Disjoint ranges -> no common elements.

Input: ([5], [5])

Expected Output: [[0, 0]]

Explanation: Single matching element.

Input: ([-3,-1,0,2], [-3,0,2,5])

Expected Output: [[0, 0], [2, 1], [3, 2]]

Explanation: Negatives handled the same way under merge.

Input: ([1,2,3,4,5], [1,2,3,4,5])

Expected Output: [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]

Explanation: Identical arrays -> every index pairs with itself.

Hints

Walk both arrays with two pointers i and j, advancing the pointer at the smaller value.
When arr1[i] == arr2[j], record [i, j] and advance BOTH pointers.
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).

Examples

Input: ([1,1,4,5,6,6,6,7,9], [1,2,3,6,6,9,9])

Expected Output: [[0, 0], [1, 0], [4, 3], [4, 4], [5, 3], [5, 4], [6, 3], [6, 4], [8, 5], [8, 6]]

Explanation: Value 1: 2x1=2 pairs; value 6: 3x2=6 pairs; value 9: 1x2=2 pairs.

Input: ([1,4,5,6,7,9], [1,2,3,6,9])

Expected Output: [[0, 0], [3, 3], [5, 4]]

Explanation: No duplicates -> reduces to the basic case.

Input: ([], [1,1,2])

Expected Output: []

Explanation: First array empty -> no pairs.

Input: ([2,2,2], [])

Expected Output: []

Explanation: Second array empty -> no pairs.

Input: ([1,2,3], [4,5,6])

Expected Output: []

Explanation: No common values.

Input: ([5,5], [5,5,5])

Expected Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2]]

Explanation: Full 2x3 Cartesian product for the shared value 5.

Input: ([-2,-2,0], [-2,0,0])

Expected Output: [[0, 0], [1, 0], [2, 1], [2, 2]]

Explanation: Value -2: 2x1; value 0: 1x2; negatives handled identically.

Hints

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

Quick Overview

This question evaluates the ability to work with sorted arrays, index mapping, duplicate handling, and reasoning about correctness and algorithmic complexity.