algoadvance

You are given two integer arrays arr1 and arr2, and an integer d.

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

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

Clarifying Questions

1. What are the constraints on the input sizes?
   • The arrays arr1 and arr2 each have lengths between 1 and 500.
   • The elements in both arrays and d are all integers between -10000 and 10000.
2. Do we need to handle inputs where arr1 or arr2 might be empty?
   • No, per constraints, arr1 and arr2 will always be non-empty.
3. What should the function return?
   • The function should return the “distance value” as defined above.

Strategy

• The simplest approach is to use brute force, where for each element in arr1, we check all elements in arr2 to see if the condition |arr1[i] - arr2[j]| <= d is violated.
• A more optimized approach could involve sorting arr2 and using binary search to find if there’s any element within the range [arr1[i] - d, arr1[i] + d].

We’ll start with the brute force approach for simplicity.

Code

from bisect import bisect_left, bisect_right

def findTheDistanceValue(arr1, arr2, d):
    arr2.sort()  # Sort arr2 to apply binary search
    distance_value = 0
    
    for num in arr1:
        # Find the position where the current number should fit in sorted arr2
        left = bisect_left(arr2, num - d)
        right = bisect_right(arr2, num + d)
        
        # If no element in arr2 is within the range
        if left == right:
            distance_value += 1
    
    return distance_value

# Example runs
print(findTheDistanceValue([4,5,8], [10,9,1,8], 2))  # Output: 2
print(findTheDistanceValue([1,4,2,3], [-4,-3,6,10,20,30], 3))  # Output: 2
print(findTheDistanceValue([2,1,100,3], [-5,-2,10,-3,7], 6))  # Output: 1

Time Complexity

• Sorting arr2 takes O(n log n), where n is the length of arr2.
• For each element in arr1, we perform a binary search which is O(log n).
• Hence, the overall time complexity is O(m log n), where m is the length of arr1 and n is the length of arr2.

This approach ensures efficient computation even when the input sizes are at their upper limits.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?