Find The Distance Value Between Two Arrays - Leetcode Solution

Problem Statement: Given two integer arrays arr1 and arr2, and an integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1: Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2 Output: 2 Explanation: For arr1[0]=4 we have: |4-10|=6 > d=2 |4-9|=5 > d=2 |4-1|=3 > d=2 |4-8|=4 > d=2 For arr1[1]=5 we have: |5-10|=5 > d=2 |5-9|=4 > d=2 |5-1|=4 > d=2 |5-8|=3 > d=2 For arr1[2]=8 we have: |8-10|=2 <= d=2 |8-9|=1 <= d=2 |8-1|=7 > d=2 |8-8|=0 <= d=2 There are 2 elements of arr1 that are not close to any element in arr2, which is [4,5].

Solution: We need to find the number of elements in arr1 that have no elements within a given distance ‘d’ present in arr2. To do this, we can use a brute force approach where we can iterate through each element in arr1 and check whether there exists any element in arr2 within the distance ‘d’ of the current element in arr1. If no such element exists, we increase a count and continue checking for the next element in arr1. Once all the elements in arr1 have been checked, we return the count as the distance value.

Code:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) { int count = 0; for(int i = 0; i < arr1.size(); i++){ int flag = 0; for(int j = 0; j < arr2.size(); j++){ if(abs(arr1[i] - arr2[j]) <= d){ flag = 1; break; } } if(flag == 0) count++; } return count; }

Time Complexity: O(n*m) where ‘n’ is the size of arr1 and ‘m’ is the size of arr2 Space Complexity: O(1) as we do not use any extra space other than the given arr1 and arr2 vectors.

1