Quick Overview

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

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

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.

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

Loading coding console...