algoadvance

Leetcode 1385. Find the Distance Value Between Two Arrays

Problem Statement:

Given two integer arrays arr1 and arr2, and an integer d, you need to find the distance value between the two arrays. The distance value is defined as the number of elements arr1[i] such that there is no element arr2[j] for which |arr1[i] - arr2[j]| <= d.

Clarifying Questions:

  1. Can the arrays contain duplicate elements?
    • Yes, both arrays can contain duplicate elements.
  2. What is the range of the array elements?
    • The array elements can be within the range of -10^4 to 10^4.
  3. Is there a limit on the size of the arrays?
    • Yes, each array can have up to 500 elements.

Strategy:

  1. Initialize a counter to zero to keep track of the distance value.
  2. For each element in arr1, check if there is any element in arr2 such that the absolute difference |arr1[i] - arr2[j]| is less than or equal to d.
  3. If no such element exists for a given arr1[i], increment the counter.
  4. Return the counter after examining all elements in arr1.

Time Complexity:

Code:

Here is the optimized approach using sorting and binary search in C++:

#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>

int findTheDistanceValue(std::vector<int>& arr1, std::vector<int>& arr2, int d) {
    std::sort(arr2.begin(), arr2.end());
    int distanceValue = 0;

    for (int num : arr1) {
        // Binary search to find the position in arr2 where this element could be
        auto lower_bound_pos = std::lower_bound(arr2.begin(), arr2.end(), num - d);
        auto upper_bound_pos = std::upper_bound(arr2.begin(), arr2.end(), num + d);

        // If there is no element in the valid range, increment the count
        if (lower_bound_pos == upper_bound_pos) {
            distanceValue++;
        }
    }
    return distanceValue;
}

int main() {
    std::vector<int> arr1 = {4, 5, 8};
    std::vector<int> arr2 = {10, 9, 1, 8};
    int d = 2;
    std::cout << "Distance Value: " << findTheDistanceValue(arr1, arr2, d) << std::endl;
    
    return 0;
}

Explanation:

  1. Sorting: First, we sort arr2 to enable binary search.
  2. Binary Search: For each element in arr1, we use std::lower_bound and std::upper_bound to find the range in arr2 where elements fall within [num - d, num + d].
  3. Count and Increment: If the positions found by lower_bound and upper_bound are the same, it means there is no element in arr2 within the distance d from the current element in arr1. Hence, we increment the distanceValue.
  4. Output: Finally, we return and print the distance value.

This approach ensures that we perform the distance check efficiently by leveraging sorting and binary search, yielding a time complexity of (O(n \log m)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI