Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1385.html

1385. Find the Distance Value Between Two Arrays (Easy)

Given two integer arrays arr1 and arr2, and the 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

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

 

Constraints:

  • 1 <= arr1.length, arr2.length <= 500
  • -10^3 <= arr1[i], arr2[j] <= 10^3
  • 0 <= d <= 100

Related Topics:
Array

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/find-the-distance-value-between-two-arrays/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int findTheDistanceValue(vector<int>& A, vector<int>& B, int d) {
        int ans = 0;
        for (int i = 0; i < A.size(); ++i) {
            bool found = false;
            for (int j = 0; j < B.size() && !found; ++j) {
                if (abs(A[i] - B[j]) <= d) found = true;
            }
            if (!found) ++ans;
        }
        return ans;
    }
};

Solution 2. Brute Force

// OJ: https://leetcode.com/problems/find-the-distance-value-between-two-arrays/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int findTheDistanceValue(vector<int>& A, vector<int>& B, int d) {
        return count_if(begin(A), end(A), [&](const auto &a) {
            return all_of(begin(B), end(B), [&](const auto &b) {
                return abs(a - b) > d;
            });
        });
    }
};

For each A[i], find the length of range [A[i] - d, A[i] + d] in array B. If the length is 0, then increment the answer.

The start point of the range (A[i] - d) can be found using lower_bound(begin(B), end(B), A[i] - d).

The next element after the end point of the range (the element after A[i] + d) can be found using upper_bound(begin(B), end(B), n + d).

If these two iterators are the same, it means the length of the range is 0.

// OJ: https://leetcode.com/problems/find-the-distance-value-between-two-arrays/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int findTheDistanceValue(vector<int>& A, vector<int>& B, int d) {
        sort(begin(B), end(B));
        int ans = 0;
        for (int n : A) {
            if (lower_bound(begin(B), end(B), n - d) == upper_bound(begin(B), end(B), n + d)) ++ans;
        }
        return ans;
    }
};

  • class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int count = 0;
        int length1 = arr1.length, length2 = arr2.length;
        for (int i = 0; i < length1; i++) {
            int num1 = arr1[i];
            boolean flag = true;
            for (int j = 0; j < length2; j++) {
                int num2 = arr2[j];
                if (Math.abs(num1 - num2) <= d) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                count++;
        }
        return count;
    }
}

############

class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int ans = 0;
        for (int a : arr1) {
            if (check(arr2, a, d)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean check(int[] arr, int a, int d) {
        for (int b : arr) {
            if (Math.abs(a - b) <= d) {
                return false;
            }
        }
        return true;
    }
}

  • // OJ: https://leetcode.com/problems/find-the-distance-value-between-two-arrays/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int findTheDistanceValue(vector<int>& A, vector<int>& B, int d) {
        int ans = 0;
        for (int i = 0; i < A.size(); ++i) {
            bool found = false;
            for (int j = 0; j < B.size() && !found; ++j) {
                if (abs(A[i] - B[j]) <= d) found = true;
            }
            if (!found) ++ans;
        }
        return ans;
    }
};

  • class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        return sum(all(abs(a - b) > d for b in arr2) for a in arr1)



  • func findTheDistanceValue(arr1 []int, arr2 []int, d int) int {
	check := func(arr []int, a int) bool {
		for _, b := range arr {
			if -d <= a-b && a-b <= d {
				return false
			}
		}
		return true
	}

	ans := 0
	for _, a := range arr1 {
		if check(arr2, a) {
			ans++
		}
	}
	return ans
}

  • function findTheDistanceValue(
    arr1: number[],
    arr2: number[],
    d: number,
): number {
    arr2.sort((a, b) => a - b);
    const n = arr2.length;
    let res = 0;
    for (const num of arr1) {
        let left = 0;
        let right = n - 1;
        while (left < right) {
            const mid = (left + right) >>> 1;
            if (arr2[mid] <= num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (
            Math.abs(num - arr2[left]) <= d ||
            (left !== 0 && Math.abs(num - arr2[left - 1]) <= d)
        ) {
            continue;
        }
        res++;
    }
    return res;
}


  • impl Solution {
    pub fn find_the_distance_value(arr1: Vec<i32>, mut arr2: Vec<i32>, d: i32) -> i32 {
        arr2.sort();
        let n = arr2.len();
        let mut res = 0;
        for &num in arr1.iter() {
            let mut left = 0;
            let mut right = n - 1;
            while left < right {
                let mid = left + (right - left) / 2;
                if arr2[mid] <= num {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            if i32::abs(num - arr2[left]) <= d || (left != 0 && i32::abs(num - arr2[left - 1]) <= d)
            {
                continue;
            }
            res += 1;
        }
        res
    }
}

All Problems

All Solutions