Maximum Distance Between a Pair of Values

Medium
759.

Maximum Distance Between a Pair of Values

Maximum Distance Between a Pair of Values is a medium coding problem on arrays, binary search and two pointers, asked in Amazon, Google and Flipkart interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var maxDistance = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Distance Between a Pair of Values — Solution

Maximum Distance Between a Pair of Values solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Distance Between a Pair of Values is a medium coding problem on arrays, binary search and two pointers, asked in Amazon, Google and Flipkart interviews.

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.

Hints for Maximum Distance Between a Pair of Values

  1. Hint 1

    Both arrays decrease, so once nums1[i] is too large for nums2[j], it is too large for every later j too — advance i.

  2. Hint 2

    Otherwise the pair is valid, so record j - i and try a larger j.

  3. Hint 3

    Neither pointer ever moves backwards, which makes the sweep linear.

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

  1. Start i and j at 0 and best at 0.
  2. If nums1[i] > nums2[j], the pair is invalid, so increment i.
  3. Otherwise the pair is valid: record j - i and increment j.
  4. 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

Java

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

C++

int maxDistance(vector<int>& nums1, vector<int>& nums2) {
    int i = 0, j = 0, best = 0;
    while (i < (int) nums1.size() && j < (int) nums2.size()) {
        if (nums1[i] > nums2[j]) i++;
        else {
            best = max(best, j - i);
            j++;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search