Is Maximum Distance Between a Pair of Values easy or hard?

Maximum Distance Between a Pair of Values is rated Medium on LeetCode with an acceptance rate around 54%. The logic becomes straightforward once you recognize the sorted property and apply a two-pointer scan instead of checking every possible pair.

Maximum Distance Between a Pair of Values Python/Java solution

Most implementations use the two-pointer method in Python, Java, C++, or JavaScript. Maintain indices i and j, check the condition nums1[i] ≤ nums2[j], update the maximum distance, and move pointers accordingly. The code runs in O(n + m) time and constant space.

How to solve Maximum Distance Between a Pair of Values in O(n)?

Use two pointers starting at index 0 for both arrays. If nums1[i] ≤ nums2[j], update the maximum distance and move j forward to attempt a larger gap. If nums1[i] > nums2[j], move i forward to reduce the value and restore the condition. Since each pointer only moves forward, the algorithm runs in linear time.

What is the best approach for Maximum Distance Between a Pair of Values?

The two-pointer technique is the optimal approach. Because both arrays are sorted in non-increasing order, you can move two indices across the arrays and expand the valid distance while maintaining the constraint nums1[i] ≤ nums2[j]. This runs in O(n + m) time with O(1) space and is the method most interviewers expect.

Is Maximum Distance Between a Pair of Values asked at Google/Amazon/Meta?

Problems combining sorted arrays with two-pointer traversal frequently appear in interviews at companies like Amazon, Google, and Meta. This question specifically tests recognition of monotonic order and efficient pointer movement instead of brute-force comparisons.

What data structure is used in Maximum Distance Between a Pair of Values?

The problem primarily uses arrays along with algorithmic patterns such as two pointers and binary search. No additional data structures are required because the arrays are already sorted, allowing efficient traversal and lookups.

What is the time complexity of Maximum Distance Between a Pair of Values?

The optimal solution runs in O(n + m) time using a two-pointer scan across both arrays. Each pointer moves forward at most once per element. A secondary solution uses binary search for each element of nums1, resulting in O(n log m) time complexity.

Description Hints 2 Solution Video 10:56

1855. Maximum Distance Between a Pair of Values

Medium61.3% acceptance2 companies

You are given two non-increasing 0-indexed integer arrays nums1 and nums2.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: The valid pairs are (0,0), (0,1), and (1,1).
The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
The maximum distance is 2 with pair (2,4).

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
Both nums1 and nums2 are non-increasing.

Asked at 2 companies

Google Microsoft

Topics

Hints open one at a time

Hint 1

Since both arrays are sorted in a non-increasing way this means that for each value in the first array. We can find the farthest value smaller than it using binary search.

Hint 2

There is another solution using a two pointers approach since the first array is non-increasing the farthest j such that nums2[j] ≥ nums1[i] is at least as far as the farthest j such that nums2[j] ≥ nums1[i-1]

10:56

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution