{x}
blog image

Maximum Distance Between a Pair of Values

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.

Solution Explanation for Maximum Distance Between a Pair of Values

This problem asks to find the maximum distance between a pair of indices (i, j) such that nums1[i] <= nums2[j] and i <= j, where nums1 and nums2 are non-increasing arrays. The distance is defined as j - i.

This approach leverages the fact that both input arrays are non-increasing. For each element nums1[i], we can efficiently find the rightmost index j in nums2 that satisfies nums1[i] <= nums2[j] using binary search. This significantly reduces the time complexity compared to a brute-force approach.

Algorithm:

  1. Reverse nums2: Reversing nums2 allows us to perform binary search more easily, as we're looking for the last index j satisfying the condition.

  2. Iterate through nums1: For each element nums1[i], perform a binary search on the reversed nums2 to find the largest index j such that nums1[i] <= nums2[j] and i <= j (which is implicitly handled by starting the binary search from index i onwards).

  3. Update Maximum Distance: Calculate the distance j - i and update the maximum distance ans if necessary.

  4. Return Maximum Distance: Return the final maximum distance ans.

Time Complexity: O(m log n), where m is the length of nums1 and n is the length of nums2. The outer loop iterates m times, and the binary search within each iteration takes O(log n) time.

Space Complexity: O(1). The algorithm uses constant extra space.

Approach 2: Two Pointers

This approach uses two pointers, one for each array, to iterate through the arrays in a coordinated manner. It maintains a sliding window in nums2 and updates the max distance based on the window size and nums1[i].

Algorithm:

  1. Initialize i to 0 (pointer for nums1) and j to 0 (pointer for nums2). Initialize ans (maximum distance) to 0.

  2. Iterate through nums1 using pointer i.

  3. For each nums1[i], advance pointer j in nums2 until nums1[i] <= nums2[j] is no longer true.

  4. Update ans with the maximum of ans and j - i - 1. The -1 accounts for the fact that we have included i and j in the distance calculation.

  5. Return ans.

Time Complexity: O(m + n), where m and n are lengths of nums1 and nums2. In the worst case, both pointers traverse the entire arrays.

Space Complexity: O(1). Constant extra space is used.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, Javascript)

The code examples for both approaches are provided in the original response. Note that the two-pointer approach generally offers better performance for this problem due to its linear time complexity compared to the binary search approach's logarithmic time complexity. However, the binary search approach provides a clearer demonstration of the utilization of binary search technique for this specific problem. Choose the approach that better suits your needs and coding style.