We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Distance Value Between Two Arrays

Number: 1486

Difficulty: Easy

Paid? No

Companies: Google, Uber

Problem Description

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] for which no element arr2[j] exists such that |arr1[i] - arr2[j]| <= d.

Key Insights

  • Sorting arr2 lets you efficiently check for the existence of an element close to a given arr1 element.
  • Binary search can be used on the sorted arr2 to quickly find the candidate(s) that are nearest to a given number from arr1.
  • Edge cases include checking the boundary elements when using binary search.

Space and Time Complexity

Time Complexity: O(n log m) where n is the length of arr1 and m is the length of arr2 (due to sorting arr2 and performing binary search for each element in arr1).
Space Complexity: O(m) for storing the sorted version of arr2.

Solution

The approach is as follows:

  1. Sort arr2 to enable binary search.
  2. For each element x in arr1, use binary search to find the insertion index in the sorted arr2.
  3. Check the candidate at the found index and its neighbor (if it exists) to determine the minimum absolute difference between x and the elements in arr2.
  4. If the minimum difference is greater than d, x contributes to the distance value.
  5. Sum up all such valid elements from arr1 and return the count.

Data Structures and Algorithms:

  • Array (for storing and iterating the numbers).
  • Sorting for arr2.
  • Binary Search for efficient nearest element lookup.

Code Solutions

# Python solution using binary search
import bisect

def findTheDistanceValue(arr1, arr2, d):
    # Sort arr2 to perform binary search
    arr2.sort()
    distance_value = 0
    
    # Iterate over each element in arr1
    for value in arr1:
        # Find the insertion index for value in arr2
        index = bisect.bisect_left(arr2, value)
        valid = True
        
        # Check the candidate on the right side if exists
        if index < len(arr2) and abs(arr2[index] - value) <= d:
            valid = False
        
        # Check the candidate on the left side if exists
        if index > 0 and abs(arr2[index - 1] - value) <= d:
            valid = False
        
        # If both checks are valid, increment the distance value count
        if valid:
            distance_value += 1
            
    return distance_value

# Example usage:
# print(findTheDistanceValue([4,5,8], [10,9,1,8], 2))  # Expected output: 2
← Back to All Questions