Maximum Distance Between a Pair of Values

medium two pointers array greedy

Problem

You are given two non-increasing integer arrays nums1 and nums2 (each sorted from largest to smallest). A pair of indices (i, j) is valid when i <= j and nums1[i] <= nums2[j]. Its distance is j − i. Return the largest distance over all valid pairs, or 0 if no valid pair exists.

Inputnums1 = [55, 30, 5, 4, 2], nums2 = [100, 20, 10, 10, 5]

Output2

The pair (i=2, j=4) is valid because 2 <= 4 and nums1[2]=5 <= nums2[4]=5, giving distance 4 − 2 = 2, the maximum possible.

nums1 (non-increasing, comma-separated)

nums2 (non-increasing, comma-separated)

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

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

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int i = 0, j = 0, ans = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] > nums2[j]) {
                i++;
            } else {
                ans = Math.max(ans, j - i);
                j++;
            }
        }
        return ans;
    }
}

int maxDistance(vector<int>& nums1, vector<int>& nums2) {
    int i = 0, j = 0, ans = 0;
    while (i < (int)nums1.size() && j < (int)nums2.size()) {
        if (nums1[i] > nums2[j]) {
            i++;
        } else {
            ans = max(ans, j - i);
            j++;
        }
    }
    return ans;
}

Explanation

We want a valid pair (i, j) with i <= j and nums1[i] <= nums2[j] whose distance j − i is as large as possible. Trying every pair is O(n²); the sorted structure lets us do far better with two indices that only ever move forward.

Keep i walking through nums1 and j walking through nums2. At each moment, compare nums1[i] with nums2[j]:

If nums1[i] > nums2[j], this i can never pair with the current j (the condition fails), and because nums2 is non-increasing, every later j is even smaller — so i is hopeless against this position. Advance i to try a smaller value from nums1.

Otherwise nums1[i] <= nums2[j], so (i, j) is valid. Record the distance j − i if it beats our best, then push j forward to greedily reach for a wider gap. We never need to move i back, because keeping the smaller i can only make the distance larger for any future j that still satisfies the value condition.

Example: nums1 = [55, 30, 5, 4, 2], nums2 = [100, 20, 10, 10, 5]. We slide i down to index 2 (value 5) where 55, 30 were both too big against 20, then let j run from index 1 to 4. The widest valid gap lands at (i=2, j=4) with 5 <= 5, distance 2.

Each index advances at most n times and never rewinds, so the whole scan is linear with only a couple of counters of extra memory.

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