Maximum Distance Between a Pair of Values - Solution & Explanation

Problem Overview: You are given two non-increasing arrays nums1 and nums2. A pair of indices (i, j) is valid if i ≤ j and nums1[i] ≤ nums2[j]. The goal is to compute the maximum distance j - i among all valid pairs.

The key constraint is that both arrays are sorted in non-increasing order. That property allows you to avoid brute force comparisons and instead scan efficiently using pointer movement or binary search.

Approach 1: Two-Pointer Technique (O(n + m) time, O(1) space)

This is the optimal solution. Maintain two pointers i for nums1 and j for nums2. Start both at index 0. If nums1[i] ≤ nums2[j], the pair is valid, so update the maximum distance j - i and move j forward to try increasing the distance. If the condition fails (nums1[i] > nums2[j]), move i forward because the current value in nums1 is too large to form a valid pair with the current j.

The sorted nature of the arrays guarantees that once a value fails the condition, increasing j will not help until i moves. Each pointer moves at most once per element, so the scan is linear. This pattern is a classic application of the two pointers technique on sorted data. Time complexity is O(n + m) and space complexity is O(1).

Approach 2: Binary Search Optimization (O(n log m) time, O(1) space)

Another way to exploit the sorted order is to fix an index i in nums1 and search for the farthest valid index in nums2. Because nums2 is non-increasing, the valid region where nums2[j] ≥ nums1[i] forms a prefix. Use binary search to find the rightmost index that satisfies the condition while also ensuring j ≥ i.

For each i, perform a search in the range [i, nums2.length - 1]. If the found index is j, update the answer with j - i. This approach repeatedly performs logarithmic searches over nums2. The total complexity becomes O(n log m) with constant extra memory. This technique highlights how sorted arrays enable efficient lookups using binary search instead of scanning.

Both approaches rely on the monotonic ordering of the arrays. Without that property, you'd need far more comparisons. These patterns commonly appear in array problems involving distance, pairing constraints, or monotonic traversal.

Recommended for interviews: The two-pointer solution is what interviewers expect. It runs in linear time, uses constant space, and demonstrates that you recognize how sorted arrays enable coordinated pointer movement. Showing the binary search alternative is useful when discussing tradeoffs or when you want to emphasize how monotonic structure enables logarithmic lookups.