Find the Distance Value Between Two Arrays

Problem Description

Ah, the classic dilemma of finding distance values between two arrays! Imagine you’re at a party, and you want to find out how many of your friends are standing far enough away from you that you can’t hear their embarrassing stories. In this problem, we have two arrays, arr1 and arr2, and a distance value d. The goal is to determine how many elements in arr1 are considered “far” from all elements in arr2 based on the distance d.

In simpler terms, if the absolute difference between an element in arr1 and any element in arr2 is greater than d, then that element in arr1 is counted. So, if you’re looking for some peace and quiet at that party, this problem is for you!

Code Solution


class Solution:
    def findTheDistanceValue(
        self,
        arr1: list[int],
        arr2: list[int],
        d: int,
    ) -> int:
        ans = 0

        arr2.sort()

        for a in arr1:
            i = bisect.bisect_left(arr2, a)
            if ((i == len(arr2) or arr2[i] - a > d) and
                    (i == 0 or a - arr2[i - 1] > d)):
                ans += 1

        return ans

Approach Explanation

The code begins by sorting arr2, which allows us to efficiently find the position of each element in arr1 using binary search. For each element a in arr1, we check if it is “far” from the closest elements in arr2. If both the closest larger and smaller elements are more than d away, we increment our answer. This way, we ensure that we only count elements in arr1 that are sufficiently distant from all elements in arr2.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log m)
Space Complexity	O(1)

Real-World Example

Let’s say you’re at a crowded concert, and you want to find out how many of your friends are standing far enough away that you can’t hear them yelling your name. If your friends are represented by arr1 and the loud concert-goers by arr2, you can use this algorithm to determine how many of your friends are blissfully unaware of your presence, thus allowing you to enjoy the music in peace!