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] <= 105nums1 and nums2 are non-increasing.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * log(m)), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Two-Pointer Technique | Time Complexity: O(n + m), where n and m are lengths of nums1 and nums2 respectively. |
| 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. |
Find K-th Smallest Pair Distance - Leetcode 719 - Python • NeetCodeIO • 17,861 views views
Watch 9 more video solutions →Practice Maximum Distance Between a Pair of Values with our built-in code editor and test cases.
Practice on FleetCode