Maximum Distance Between a Pair of Values — Medium Problem & Solution

Both nums1 and nums2 are sorted in non-increasing order. A pair (i, j) is valid when i <= j and nums1[i] <= nums2[j].

Difficulty: Medium
Topics: Arrays, Two Pointers, Binary Search
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Both nums1 and nums2 are sorted in non-increasing order. A pair (i, j) is valid when i <= j and nums1[i] <= nums2[j].

Return the maximum value of j - i over all valid pairs, or 0 if none exists.

Example 1

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The pair (2, 4) is valid since 5 <= 5, giving a distance of 2.

Example 2

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: (0, 1) is valid.

Example 3

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: (2, 4) is valid since 19 <= 25.

Constraints

1 <= nums1.length, nums2.length <= 100000
1 <= values <= 1000000000
Both arrays are non-increasing.

How to solve Maximum Distance Between a Pair of Values

Sweep both arrays with forward-only pointers. When the pair is invalid the left pointer must advance; when it is valid the right pointer can advance to look for a wider gap.

Approach

Start i and j at 0 and best at 0.
If nums1[i] > nums2[j], the pair is invalid, so increment i.
Otherwise the pair is valid: record j - i and increment j.
Stop when either pointer runs off its array.

Why it works

Both arrays are non-increasing, so if nums1[i] > nums2[j] then nums1[i] > nums2[j'] for every j' >= j — no valid pair uses this i with a larger j, and smaller j would only shrink the distance. Advancing i therefore loses nothing.

Complexity

Time — O(n + m)
Space — O(1)

Pitfalls

i <= j is required, but the sweep maintains it automatically because i only advances while i <= j.
Starting best above 0 breaks the 'no valid pair' case.
The arrays are non-increasing, not non-decreasing; reversing the comparison breaks the invariant.

Reference solution

Python

from typing import List

def maxDistance(nums1: List[int], nums2: List[int]) -> int:
    i = j = best = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] > nums2[j]:
            i += 1
        else:
            best = max(best, j - i)
            j += 1
    return best

JavaScript

var maxDistance = function(nums1, nums2) {
    var i = 0, j = 0, best = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] > nums2[j]) i++;
        else {
            if (j - i > best) best = j - i;
            j++;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue