Sponsored
Sponsored
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`.
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.
1#include <stdio.h>
2int maxDistance(int* nums1, int nums1Size, int* nums2, int nums2Size) {
3 int i = 0, j = 0, maxDist = 0;
4 while (i < nums1Size && j < nums2Size) {
5 if (nums1[i] <= nums2[j]) {
6 if (j - i > maxDist) {
7 maxDist = j - i;
8 }
9 j++;
10 } else {
11 i++;
12 }
13 }
14 return maxDist;
15}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.
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`.
Time Complexity: O(n * log(m)), where n is the length of nums1 and m is the length of nums2.
Space Complexity: O(1).
1#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;
}The C++ version uses an inline `binarySearch` function to determine the maximum valid `j` position for each element in `nums1` by using binary search on `nums2`.