Maximum Distance Between a Pair of Values
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach improves upon the brute-force method by optimizing the search for the index j. For each index i in nums1, instead of linearly scanning nums2, we use binary search to find the largest valid index j. This is possible because nums2 is a non-increasing (sorted) array.
Algorithm
- Initialize
maxDistance = 0. - Iterate
ifrom 0 tonums1.length - 1. - For each
i, perform a binary search onnums2in the range[i, nums2.length - 1]for the valuenums1[i]. - The goal of the binary search is to find the largest index
jsuch thatnums2[j] >= nums1[i]. - Let this index be
found_j. - If a valid
found_jexists (i.e., it's not -1), updatemaxDistance = max(maxDistance, found_j - i). - Return
maxDistance.
Walkthrough
We can optimize the inner loop of the brute-force approach. For a fixed i, we want to find the largest j such that j >= i and nums2[j] >= nums1[i]. Since nums2 is non-increasing, the values nums2[j] that are greater than or equal to nums1[i] will appear at the beginning of the array. We can use binary search to efficiently find the rightmost index j that satisfies this condition.
For each i from 0 to nums1.length - 1, we perform a binary search on the subarray nums2 starting from index i. The search aims to find the largest j where nums2[j] >= nums1[i]. If such a j is found, we calculate j - i and update our maxDistance.
class Solution { public int maxDistance(int[] nums1, int[] nums2) { int maxDistance = 0; int n = nums1.length; int m = nums2.length; for (int i = 0; i < n; i++) { // Binary search for the largest j >= i with nums2[j] >= nums1[i] int low = i; int high = m - 1; int best_j = -1; while (low <= high) { int mid = low + (high - low) / 2; if (nums2[mid] >= nums1[i]) { // This is a potential answer, try to find a larger j best_j = mid; low = mid + 1; } else { // nums2[mid] is too small, need to search in the left part high = mid - 1; } } if (best_j != -1) { maxDistance = Math.max(maxDistance, best_j - i); } } return maxDistance; }}Complexity
Time
O(N * log M), where N is the length of `nums1` and M is the length of `nums2`. The outer loop runs N times, and each binary search takes O(log M) time.
Space
O(1), as we only use a few variables for the loops and binary search.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Passes the time limits for the given constraints.
Cons
More complex to implement correctly than the brute-force approach.
Not as efficient as the optimal two-pointer solution.
This is the most efficient approach, leveraging the non-increasing property of both arrays. We use two pointers, i for nums1 and j for nums2, to traverse the arrays in a single combined pass, achieving linear time complexity.
Algorithm
- Initialize
i = 0(pointer fornums1) andmaxDistance = 0. - Iterate
jfrom 0 tonums2.length - 1(pointer fornums2). - Inside the loop, advance pointer
ias long asi < nums1.lengthandnums1[i] > nums2[j]. This finds the firstithat could potentially form a valid pair withj. - After the inner
whileloop, ifi < nums1.lengthandi <= j, we have a valid pair(i, j). - Update
maxDistance = max(maxDistance, j - i). - Since
iis the smallest possible index for the currentj,j-iis the maximum possible distance for thisj. - Return
maxDistanceafter the loop finishes.
Walkthrough
The key insight for the two-pointer approach is that as we iterate through j in nums2, the corresponding best i in nums1 will also only move forward. Let's iterate through nums2 with a pointer j. For each j, we want to find the smallest i such that i <= j and nums1[i] <= nums2[j]. A smaller i maximizes the distance j - i.
We can maintain a second pointer i for nums1. For a given j, if nums1[i] is too large (i.e., nums1[i] > nums2[j]), then we must increment i to find a smaller value in nums1. Since nums1 is non-increasing, any index less than the current i would also have a value greater than nums2[j], so we don't need to consider them. This means the pointer i never needs to be reset.
Both pointers i and j only move from left to right, ensuring that each element in both arrays is visited at most once.
class Solution { public int maxDistance(int[] nums1, int[] nums2) { int i = 0; int maxDistance = 0; int n = nums1.length; int m = nums2.length; for (int j = 0; j < m; j++) { // For the current j, find the smallest i such that nums1[i] <= nums2[j]. // The pointer i only moves forward. while (i < n && nums1[i] > nums2[j]) { i++; } // If we found such an i and it's a valid pair (i <= j) if (i < n && i <= j) { maxDistance = Math.max(maxDistance, j - i); } } return maxDistance; }}Complexity
Time
O(N + M), where N is the length of `nums1` and M is the length of `nums2`. Each pointer traverses its respective array at most once.
Space
O(1), as it only requires a few variables to store pointers and the result.
Trade-offs
Pros
Optimal time complexity.
Very efficient as it processes both arrays in a single pass.
Simple implementation once the logic is understood.
Cons
The logic can be less intuitive to derive compared to the other approaches.
This approach involves checking every possible valid pair of indices (i, j) and calculating their distance. We iterate through all i from nums1 and for each i, we iterate through all j from nums2 such that j >= i. If the pair is valid, we update the maximum distance found.
Algorithm
- Initialize a variable
maxDistanceto 0. - Use a nested loop. The outer loop iterates through
nums1with indexifrom 0 tonums1.length - 1. - The inner loop iterates through
nums2with indexjfromitonums2.length - 1. This ensures thei <= jcondition. - Inside the inner loop, check if
nums1[i] <= nums2[j]. - If the condition is true, it's a valid pair. Calculate the distance
j - iand updatemaxDistance = max(maxDistance, j - i). - After the loops complete,
maxDistancewill hold the result.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We can simply translate the problem statement into code. We need to find the maximum j - i among all pairs (i, j) that satisfy two conditions: i <= j and nums1[i] <= nums2[j]. We can use two nested loops to generate all possible pairs (i, j) where i <= j. The outer loop iterates i from 0 to nums1.length - 1, and the inner loop iterates j from i to nums2.length - 1. Inside the inner loop, we check the second condition, nums1[i] <= nums2[j]. If it holds, we have a valid pair, and we update our maxDistance with the current distance j - i if it's larger.
class Solution { public int maxDistance(int[] nums1, int[] nums2) { int maxDistance = 0; int n = nums1.length; int m = nums2.length; for (int i = 0; i < n; i++) { for (int j = i; j < m; j++) { if (nums1[i] <= nums2[j]) { maxDistance = Math.max(maxDistance, j - i); } } } return maxDistance; }}Complexity
Time
O(N * M), where N is the length of `nums1` and M is the length of `nums2`. For each element in `nums1`, we potentially iterate through a large portion of `nums2`.
Space
O(1), as we only use a constant amount of extra space for variables.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient due to the nested loops.
Will result in a 'Time Limit Exceeded' error for large input sizes as specified in the constraints.
Solutions
Solution
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var maxDistance = function (nums1, nums2) { 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; };class Solution {public int maxDistance(int[] nums1, int[] nums2) { int ans = 0; int m = nums1.length, n = nums2.length; for (int i = 0; i < m; ++i) { int left = i, right = n - 1; while (left < right) { int mid = (left + right + 1) >> 1; if (nums2[mid] >= nums1[i]) { left = mid; } else { right = mid - 1; } } ans = Math.max(ans, left - i); } return ans; }}class Solution {public: int maxDistance(vector<int> &nums1, vector<int> &nums2) { int ans = 0; reverse(nums2.begin(), nums2.end()); for (int i = 0; i < nums1.size(); ++i) { int j = nums2.size() - (lower_bound(nums2.begin(), nums2.end(), nums1[i]) - nums2.begin()) - 1; ans = max(ans, j - i); } return ans; }};class Solution: def maxDistance(self, nums1: List[int], nums2: List[int]) -> int: ans = 0 nums2 = nums2[:: - 1] for i, v in enumerate(nums1): j = len(nums2) - bisect_left(nums2, v) - 1 ans = max(ans, j - i) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.