Maximum Distance Between a Pair of Values solution and explanation
Google
9 more videos on this problem
LeetCode Weekly Contest 240 Question 2 Maximum Distance Between a Pair of ValuesCoding Ninjas Webinars and Contest Editorials · 10:56 · 1K views
1855. Maximum Distance Between a Pair of Values (Leetcode Medium)Programming Live with Larry · 18:10 · 823 views
1855. Maximum Distance Between a Pair of Values | Leetcode Daily - PythonLeetcode Daily · 4:46 · 309 views
LC 1855 Maximum Distance Between a Pair of ValuesRoger Sentongo (rnt) · 11:47 · 152 views
Maximum Distance Between a Pair of Values | LeetCode 1855 | Two PointerStreak To Scale · 5:08 · 110 views
LeetCode 1855: Maximum Distance Between a Pair of Values - Two Pointer Approach in C++ TutorialNovice Coder · 12:23 · 93 views
Leetcode 1855. Maximum Distance Between a Pair of Valuesbbbb · 6:38 · 88 views
Leetcode : 1855 - Maximum Distance Between a Pair of ValuesVarun Kumar · 8:27 · 88 views
Leetcode 1855 : Maximum Distance Between a Pair of Values [ Brute + Better + Optimal ]Madhumitha Kolkar · 16:34 · 80 views
Maximum Distance Between a Pair of Values | LeetCode 1855 - Pythonimpoldev · 11:17 · 68 views
The problem
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 <= 1051 <= nums1[i], nums2[j] <= 105- Both
nums1andnums2are 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`.
def maxDistance(nums1, nums2):
i, j, max_dist = 0, 0, 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
max_dist = max(max_dist, j - i)
j += 1
else:
i += 1
return max_distclass Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int i = 0, j = 0, maxDist = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] <= nums2[j]) {
maxDist = Math.max(maxDist, j - i);
j++;
} else {
i++;
}
}
return maxDist;
}
}#include <vector>
#include <algorithm>
using namespace std;
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0, maxDist = 0;
while (i < nums1.size() && j < nums2.size()) {
if (nums1[i] <= nums2[j]) {
maxDist = max(maxDist, j - i);
j++;
} else {
i++;
}
}
return maxDist;
}var maxDistance = function(nums1, nums2) {
let i = 0, j = 0, maxDist = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] <= nums2[j]) {
maxDist = Math.max(maxDist, j - i);
j++;
} else {
i++;
}
}
return maxDist;
};#include <stdio.h>
int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int i = 0, j = 0, maxDist = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] <= nums2[j]) {
if (j - i > maxDist) {
maxDist = j - i;
}
j++;
} else {
i++;
}
}
return maxDist;
}public class Solution {
public int MaxDistance(int[] nums1, int[] nums2) {
int i = 0, j = 0, maxDist = 0;
while (i < nums1.Length && j < nums2.Length) {
if (nums1[i] <= nums2[j]) {
maxDist = Math.Max(maxDist, j - i);
j++;
} else {
i++;
}
}
return maxDist;
}
}In Python, the two-pointer technique is slipped into a function, looping through with pointer `i` on `nums1` and `j` on `nums2` to find valid pairs, updating `max_dist` accordingly.
Time Complexity: O(n + m).
Space Complexity: O(1).
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`.
def maxDistance(nums1, nums2):
def binary_search(arr, left, right, target):
while left <= right:
mid = left + (right - left) // 2
if arr[mid] < target:
right = mid - 1
else:
left = mid + 1
return right
max_dist = 0
for i in range(len(nums1)):
j = binary_search(nums2, i, len(nums2) - 1, nums1[i])
if j >= i:
max_dist = max(max_dist, j - i)
return max_distclass Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int maxDist = 0;
for (int i = 0; i < nums1.length; ++i) {
int j = binarySearch(nums2, i, nums2.length - 1, nums1[i]);
if (j >= i) {
maxDist = Math.max(maxDist, j - i);
}
}
return maxDist;
}
private int binarySearch(int[] nums, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
}#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(vector<int>& arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int maxDist = 0;
for (int i = 0; i < nums1.size(); ++i) {
int j = binarySearch(nums2, i, nums2.size() - 1, nums1[i]);
if (j >= i) {
maxDist = max(maxDist, j - i);
}
}
return maxDist;
}var maxDistance = function(nums1, nums2) {
const binarySearch = (arr, left, right, target) => {
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
if (arr[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
};
let maxDist = 0;
for (let i = 0; i < nums1.length; ++i) {
const j = binarySearch(nums2, i, nums2.length - 1, nums1[i]);
if (j >= i) {
maxDist = Math.max(maxDist, j - i);
}
}
return maxDist;
};#include <stdio.h>
#include <stdbool.h>
int binarySearch(int* arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int maxDist = 0;
for (int i = 0; i < nums1Size; ++i) {
int j = binarySearch(nums2, i, nums2Size - 1, nums1[i]);
if (j >= i) {
int dist = j - i;
if (dist > maxDist) {
maxDist = dist;
}
}
}
return maxDist;
}public class Solution {
public int MaxDistance(int[] nums1, int[] nums2) {
int maxDist = 0;
for (int i = 0; i < nums1.Length; ++i) {
int j = BinarySearch(nums2, i, nums2.Length - 1, nums1[i]);
if (j >= i) {
maxDist = Math.Max(maxDist, j - i);
}
}
return maxDist;
}
private int BinarySearch(int[] arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return right;
}
}The Python solution incorporates binary search to quickly locate the farthest valid `j` for each `i`, enhancing performance while maintaining simplicity.
Time Complexity: O(n * log(m)).
Space Complexity: O(1).
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).
function maxDistance(nums1: number[], nums2: number[]): number {
let ans = 0;
let m = nums1.length;
let n = nums2.length;
for (let i = 0; i < m; ++i) {
let left = i;
let right = n - 1;
while (left < right) {
const mid = (left + right + 1) >> 1;
if (nums2[mid] >= nums1[i]) {
left = mid;
} else {
right = mid - 1;
}
}
ans = Math.max(ans, left - i);
}
return ans;
}func maxDistance(nums1 []int, nums2 []int) int {
ans, n := 0, len(nums2)
for i, num := range nums1 {
left, right := i, n-1
for left < right {
mid := (left + right + 1) >> 1
if nums2[mid] >= num {
left = mid
} else {
right = mid - 1
}
}
if ans < left-i {
ans = left - i
}
}
return ans
}impl Solution {
pub fn max_distance(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let m = nums1.len();
let n = nums2.len();
let mut res = 0;
for i in 0..m {
let mut left = i;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
if nums2[mid] >= nums1[i] {
left = mid + 1;
} else {
right = mid;
}
}
res = res.max((left - i - 1) as i32);
}
res
}
}Approach 4: Default Approach
function maxDistance(nums1: number[], nums2: number[]): number {
let ans = 0;
const m = nums1.length;
const n = nums2.length;
for (let i = 0, j = 0; i < m; ++i) {
while (j < n && nums1[i] <= nums2[j]) {
j++;
}
ans = Math.max(ans, j - i - 1);
}
return ans;
}func maxDistance(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
ans := 0
for i, j := 0, 0; i < m; i++ {
for j < n && nums1[i] <= nums2[j] {
j++
}
if ans < j-i-1 {
ans = j - i - 1
}
}
return ans
}impl Solution {
pub fn max_distance(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let m = nums1.len();
let n = nums2.len();
let mut res = 0;
let mut j = 0;
for i in 0..m {
while j < n && nums1[i] <= nums2[j] {
j += 1;
}
res = res.max((j - i - 1) as i32);
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n + m). |
| Approach 2: Binary Search Optimization | Time Complexity: O(n * log(m)). |
| Binary Search | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n + m) | O(1) | Best choice when both arrays are sorted in non-increasing order and you want a linear scan. |
| Binary Search Optimization | O(n log m) | O(1) | Useful when you want to search the farthest valid index for each element using the sorted property. |
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.