.png&w=3840&q=75)
This problem () asks you to find the maximum distance j - i such that:
i <= jnums1[i] <= nums2[j]- Both arrays are non-increasing (sorted in descending order)
Key Idea
Since both arrays are sorted in descending order, you can use a two-pointer approach:
- Start with
i = 0andj = 0 - If
nums1[i] <= nums2[j], it's valid → update answer and movej++(try to increase distance) - Otherwise → move
i++(need a smaller value innums1)
This works in O(n + m) time.
C++ Solution
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
int n = nums1.size(), m = nums2.size();
int maxDist = 0;
while (i < n && j < m) {
if (nums1[i] <= nums2[j]) {
maxDist = max(maxDist, j - i);
j++; // try to expand distance
} else {
i++; // need smaller nums1[i]
}
}
return maxDist;
}
};