Maximum Distance Between a Pair of Values

Maximum Distance Between a Pair of Values

1. What is this problem about?

The Maximum Distance Between a Pair of Values problem involves two non-increasing arrays, nums1 and nums2. A pair of indices (i, j) is considered 'valid' if i <= j, nums1[i] <= nums2[j], and i is from the first array while j is from the second. The goal is to find the maximum possible distance j - i among all valid pairs. If no such pair exists, the distance is 0. This problem focuses on efficiently searching through two sorted or semi-sorted lists.

2. Why is this asked in interviews?

This Maximum Distance Between a Pair of Values interview question is a classic for testing Two Pointers and Binary Search techniques. Google often uses these types of problems to see if a candidate can leverage the sorted property of the input to avoid an O(N*M) exhaustive search. It tests your ability to maintain pointers across two different structures and your understanding of how index constraints (i <= j) interact with value constraints (nums1[i] <= nums2[j]).

3. Algorithmic pattern used

The most efficient approach uses the Two Pointers interview pattern. Since both arrays are non-increasing (meaning they are sorted in descending order), we can use one pointer for nums1 and another for nums2. We increment the second pointer as long as the condition nums1[i] <= nums2[j] is met and j is within bounds. This allows us to find the furthest 'j' for each 'i' in a single linear scan, resulting in O(N+M) time complexity.

4. Example explanation

Suppose nums1 = [50, 40, 20] and nums2 = [60, 45, 45, 10].

• Start i=0 (val 50), j=0 (val 60). 50 <= 60 is true. Try next j.
• i=0 (val 50), j=1 (val 45). 50 <= 45 is false. Max distance so far: j-i = 0-0 = 0.
• Move to i=1 (val 40). We start j from its previous valid position (0) or increment.
• i=1 (val 40), j=1 (val 45). 40 <= 45 is true. Try next j.
• i=1 (val 40), j=2 (val 45). 40 <= 45 is true. Try next j.
• i=1 (val 40), j=3 (val 10). 40 <= 10 is false. Max distance: 2-1 = 1.
• Move to i=2 (val 20).
• i=2 (val 20), j=2 (val 45). 20 <= 45 is true. Try next j.
• i=2 (val 20), j=3 (val 10). 20 <= 10 is false. Distance: 2-2 = 0. Max distance is 1.

5. Common mistakes candidates make

Candidates often forget the i <= j constraint, leading them to find pairs that aren't valid. Another mistake is resetting the second pointer for every new first pointer, which reverts the efficiency back to O(N*M). Some might also struggle with the 'non-increasing' property, confusing it with 'increasing' and applying the wrong logic to the pointers.

6. Interview preparation tip

When dealing with two sorted arrays, always ask yourself: 'Can I use two pointers?' or 'Can I use binary search?'. For the Maximum Distance Between a Pair of Values coding problem, both work, but two pointers is generally more elegant and faster. Practice identifying which pointer should move and under what conditions to keep the search space restricted.