Solution
The O(n*m) solution, n and m being sizes of arr1 and arr2 respectively, is pretty straightforward and surprisingly it is accepted by the LeetCode judge. Here we will see a O(max(nlogn, nlogm)) solution. The idea is to sort both the arrays and employ a two pointer approach. Let i point to index of arr1 and j point to index of arr2. We start with i=0 and j=0. Consider the following cases:
- arr1[i]>=arr2[j]
- arr1[i]-arr2[j]>d: in this case, there is a possibility that arr1[i]-arr2[j+1]<=d so we increment j. Note that this is because arr2[j+1]>=arr2[j] since we sorted the array.
- arr1[i]-arr2[j]<=d: in this case, arr1[i] should not be a part of the answer so we increment i.
- arr1[i] < arr2[j]
- arr2[j]-arr1[i]>d: now, we reach at this condition only when we know that arr1[i]-arr2[0…j-1]>d. Since arr2[j+1]>arr2[j], it is guaranteed that there is no index k such that arr2[k]-arr1[i]<=d. Hence, we increment our answer and also increment i.
- arr2[j]-arr1[i]<=d: in this case, arr1[i] should not be a part of the answer so we increment i.
Now, we might end up with iterating the whole arr2 but not iterating over all the elements of arr1. Say we could only go up till index i of arr1. As we increment j only when arr1[i]-arr2[j]>d, this means that arr1[i..arr1.size-1] should also be a part of the answer. So we add arr1.size-i to our answer finally.
Example dry run:
Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Initial Variables: i=0, j=0, res=0
Step 1: 4 < 10 and 10-4 > d so res+=1 and i+=1 // now, i=1, j=0, res=1
Step 2: 5 < 10 and 10-5 > d so res+=1 and i+=1 // now, i=2, j=0, res=2
Step 3: 8 < 10 and 10-8 <= d so i+=1 // now, i=3, j=0, res=2
Code:
int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int res = 0, i=0, j=0;
while (i<arr1.size() && j<arr2.size()) {
if (arr1[i]>=arr2[j]) {
if (arr1[i]-arr2[j]>d)
j++;
else
i++;
} else {
if (arr2[j]-arr1[i]>d) {
i++;
res++;
}
else
i++;
}
}
res += arr1.size()-i;
return res;
}
Time complexity: O(max(nlogn, mlogm))