Problem Description

You are given two integer arrays arr1 and arr2, and an integer d. Your task is to find the distance value between these two arrays.

The distance value is defined as the count of elements from arr1 that satisfy a specific condition. For an element arr1[i] to be counted, there should not be any element arr2[j] where the absolute difference between them is less than or equal to d.

In mathematical terms, an element arr1[i] contributes to the distance value if for all elements in arr2[j], the condition |arr1[i] - arr2[j]| > d holds true.

For example:

• If arr1 = [4, 5, 8], arr2 = [10, 9, 1, 8], and d = 2
• For arr1[0] = 4: Check against all elements in arr2
  • |4 - 10| = 6 > 2 ✓
  • |4 - 9| = 5 > 2 ✓
  • |4 - 1| = 3 > 2 ✓
  • |4 - 8| = 4 > 2 ✓
  • Since all differences are greater than d, this element counts.
• Similarly check for other elements in arr1
• Count all elements from arr1 that satisfy the condition

The solution uses sorting and binary search optimization. After sorting arr2, for each element x in arr1, it uses binary search to find if there's any element in the sorted arr2 within the range [x - d, x + d]. If no such element exists in this range, then x contributes to the distance value.

Intuition

The brute force approach would be to check every element in arr1 against every element in arr2, which would take O(n * m) time. However, we can optimize this by recognizing a key insight: for each element x in arr1, we need to check if there's any element in arr2 within the range [x - d, x + d].

This "range checking" problem naturally leads us to think about sorting and binary search. If we sort arr2, the elements that could potentially violate our distance requirement (those within distance d from x) would form a contiguous segment in the sorted array.

For any element x from arr1, the elements in arr2 that would make it invalid are those where |x - arr2[j]| <= d, which can be rewritten as x - d <= arr2[j] <= x + d. In a sorted arr2, all such elements would be consecutive.

Using binary search, we can quickly find the leftmost position where an element could be >= x - d. If this position doesn't exist (we've gone past the array), or if the element at this position is > x + d, then no element in arr2 is within distance d from x, meaning x contributes to our answer.

This approach reduces our time complexity from O(n * m) to O(m log m + n log m), where the first term is for sorting arr2 and the second term is for performing binary search for each element in arr1.

The beauty of this solution lies in transforming a "check all pairs" problem into a "find if any element exists in a range" problem, which can be efficiently solved with sorting and binary search.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution implements the sorting and binary search strategy to efficiently find the distance value between two arrays.

Step 1: Sort the second array

arr2.sort()

We sort arr2 to enable binary search. After sorting, elements that are close to each other in value will be adjacent, making range queries efficient.

Step 2: Process each element in arr1 For each element x in arr1, we need to check if there's any element in arr2 within the range [x - d, x + d].

Step 3: Binary search for the lower bound

i = bisect_left(arr2, x - d)

The bisect_left function finds the leftmost insertion position for x - d in the sorted arr2. This gives us the index of the first element that is greater than or equal to x - d.

Step 4: Check the condition

ans += i == len(arr2) or arr2[i] > x + d

This line checks two conditions:

• i == len(arr2): This means all elements in arr2 are less than x - d. Since the smallest possible element that could violate our condition would be x - d, and all elements are smaller than this, none of them are within distance d from x.
• arr2[i] > x + d: The element at position i is the smallest element that is >= x - d. If this element is also > x + d, then there's no element in the range [x - d, x + d], meaning no element in arr2 is within distance d from x.

If either condition is true, the current element x from arr1 contributes to the distance value, so we increment our answer.

Time Complexity: O(m log m + n log m) where n is the length of arr1 and m is the length of arr2. The sorting takes O(m log m) and we perform n binary searches, each taking O(log m).

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (which might use O(log m) for the recursion stack in some implementations).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• arr1 = [2, 1, 100]
• arr2 = [3, 5, 104]
• d = 3

Step 1: Sort arr2 After sorting: arr2 = [3, 5, 104] (already sorted in this case)

Step 2: Check each element in arr1

For arr1[0] = 2:

• We need to check if any element in arr2 is within range [2-3, 2+3] = [-1, 5]
• Binary search for -1 in sorted arr2:
  • bisect_left([3, 5, 104], -1) = 0 (position where -1 would be inserted)
  • Check: Is arr2[0] > 5?
  • arr2[0] = 3, which is NOT greater than 5
  • So element 3 is within distance 3 from 2 (|2-3| = 1 ≤ 3)
  • This element does NOT count ✗

For arr1[1] = 1:

• We need to check if any element in arr2 is within range [1-3, 1+3] = [-2, 4]
• Binary search for -2 in sorted arr2:
  • bisect_left([3, 5, 104], -2) = 0
  • Check: Is arr2[0] > 4?
  • arr2[0] = 3, which is NOT greater than 4
  • So element 3 is within distance 3 from 1 (|1-3| = 2 ≤ 3)
  • This element does NOT count ✗

For arr1[2] = 100:

• We need to check if any element in arr2 is within range [100-3, 100+3] = [97, 103]
• Binary search for 97 in sorted arr2:
  • bisect_left([3, 5, 104], 97) = 2
  • Check: Is arr2[2] > 103?
  • arr2[2] = 104, which IS greater than 103
  • No element in arr2 is within distance 3 from 100
  • This element COUNTS ✓

Final Answer: 1 (only the element 100 from arr1 satisfies the condition)

The key insight is that by sorting arr2 and using binary search, we can quickly determine if any element falls within the "forbidden" range [x-d, x+d] for each element x in arr1. If the binary search either points beyond the array or finds an element outside this range, we know that element x contributes to our distance value.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n + m log n) which simplifies to O((m + n) × log n), where m is the length of arr1 and n is the length of arr2.

Breaking down the time complexity:

• Sorting arr2 takes O(n log n) time
• For each element in arr1 (m iterations), we perform a binary search using bisect_left on the sorted arr2, which takes O(log n) time
• Total: O(n log n) + O(m × log n) = O((m + n) × log n)

The space complexity is O(log n).

The space complexity comes from:

• The sorting operation on arr2 uses O(log n) space for the recursive call stack (assuming Python uses an efficient sorting algorithm like Timsort)
• The bisect_left function uses O(1) space since it's implemented iteratively in Python
• No additional data structures are created that scale with input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Distance Condition

The Problem: A common mistake is misinterpreting what "distance value" means. Developers often incorrectly count elements from arr1 that have at least one element in arr2 with distance > d, when the correct interpretation requires all elements in arr2 to have distance > d.

Incorrect Implementation:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    count = 0
    for num1 in arr1:
        for num2 in arr2:
            if abs(num1 - num2) > d:  # Wrong! This counts if ANY element satisfies
                count += 1
                break
    return count

Correct Approach:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
    count = 0
    for num1 in arr1:
        valid = True
        for num2 in arr2:
            if abs(num1 - num2) <= d:  # Check if ANY element violates
                valid = False
                break
        if valid:
            count += 1
    return count

Pitfall 2: Off-by-One Error in Range Checking

The Problem: When using binary search, developers might incorrectly check the range boundaries. The condition should be <= d for violation, not < d.

Incorrect Implementation:

# Wrong: checking strictly less than d
is_valid = (left_bound_index == len(arr2) or arr2[left_bound_index] >= num + d)

Correct Implementation:

# Correct: an element violates if distance <= d, so we need > d
is_valid = (left_bound_index == len(arr2) or arr2[left_bound_index] > num + d)

Pitfall 3: Not Handling Edge Cases

The Problem: Forgetting to handle edge cases like empty arrays or when all elements satisfy/violate the condition.

Solution: Always test with:

• Empty arr1 or arr2
• Single element arrays
• Cases where d = 0
• Cases where all elements are valid or invalid

# Edge case examples to test:
assert findTheDistanceValue([1], [100], 50) == 0  # Distance exactly at boundary
assert findTheDistanceValue([1], [100], 98) == 0  # Just within range
assert findTheDistanceValue([1], [100], 99) == 1  # Just outside range
assert findTheDistanceValue([], [1, 2, 3], 5) == 0  # Empty arr1

Pitfall 4: Using bisect_right Instead of bisect_left

The Problem: Using bisect_right would find the rightmost insertion position, which could lead to missing elements that are exactly equal to num - d.

Example: If arr2 = [1, 3, 5, 7], num = 5, and d = 2:

• Range to check: [3, 7]
• bisect_left(arr2, 3) returns 1 (correct: points to element 3)
• bisect_right(arr2, 3) returns 2 (incorrect: skips element 3)

The correct choice is bisect_left to ensure we don't miss boundary elements.