Skip to main content
Talentd

Maximum Distance Between a Pair of Values - Solution & Explanation

MediumArrayTwo PointersBinary Search17 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums1[i], nums2[j] <= 105
  • Both nums1 and nums2 are non-increasing.

Approach Overview

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.

Approach 1: Approach 1: Two-Pointer Technique

This method employs two pointers to traverse both arrays simultaneously. Start with `i` at the beginning of `nums1` and `j` at the beginning of `nums2`. Try to find the largest `j` for each `i` while maintaining the condition `nums1[i] <= nums2[j]` and `i <= j`. The distance `j - i` is calculated and the maximum one is stored. Iterate through both arrays by incrementing `j` while ensuring the condition holds true, otherwise increment `i`.

The solution uses two pointers initialized at the start of `nums1` and `nums2`. It checks if `nums1[i] <= nums2[j]` and calculates the distance `j-i`. If valid, move `j` to explore a potential longer distance. If invalid, increment `i` to find a valid pair. The largest distance found is stored and returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n and m are lengths of nums1 and nums2 respectively.
Space Complexity: O(1), only a few variables are used.

Try this approach in the editor →

Approach 2: Approach 2: Binary Search Optimization

Utilizing binary search on `nums2` for each element in `nums1` can optimize the search for each valid `j` index. This approach leverages the sorted nature of the arrays. For each element in `nums1`, perform a binary search in `nums2` to find the farthest possible valid `j`.

This solution implements binary search on `nums2` for each element in `nums1` to find the farthest valid `j`. The results of each distance are compared and stored if maximum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log(m)), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Binary Search

Assume the lengths of nums1 and nums2 are m and n respectively.

Traverse array nums1, for each number nums1[i], perform a binary search for numbers in nums2 in the range [i,n), find the last position j that is greater than or equal to nums1[i], calculate the distance between this position and i, and update the maximum distance value ans.

The time complexity is O(m times log n), where m and n are the lengths of nums1 and nums2 respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Two-Pointer Technique

Time Complexity: O(n + m), where n and m are lengths of nums1 and nums2 respectively.
Space Complexity: O(1), only a few variables are used.

Approach 2: Binary Search Optimization

Time Complexity: O(n * log(m)), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1).

Binary Search—
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer TechniqueO(n + m)O(1)Best choice when both arrays are sorted in non-increasing order and you want a linear scan.
Binary Search OptimizationO(n log m)O(1)Useful when you want to search the farthest valid index for each element using the sorted property.

Video Solution

LeetCode Weekly Contest 240 Question 2 Maximum Distance Between a Pair of Values • Coding Ninjas Webinars and Contest Editorials • 1,200 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Maximum Distance Between a Pair of Values with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Furthest Houses With Different Colors