1385. Find the Distance Value Between Two Arrays

EasyArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

The goal of this problem is to compare two lists of integers, arr1 and arr2, and determine the number of elements in arr1 that are at least distance d apart from every element in arr2. We define this "distance value" as the count of such arr1[i] elements for which no arr2[j] exists where |arr1[i]-arr2[j]| <= d. In other words, we're counting how many elements in arr1 are not within d distance of any element in arr2.

Intuition

The key to solving this problem efficiently is to recognize that we can exploit the properties of sorted arrays. By sorting arr2, we can quickly determine if any given element in arr1 is within the distance d to elements in arr2 using binary search, rather than comparing it to every element in arr2.

The intuition behind the solution is to sort arr2 first. Then, for each element a in arr1, we perform a binary search to find the position where a - d would fit in arr2. This tells us the index of the first element in arr2 that could potentially be within distance d of a. We call the helper function check with the current element a to verify that indeed there is no arr2[j] such that |a - arr2[j]| <= d.

Since arr2 is sorted, if the element at the found index is greater than a + d, then a is not within distance d of any element in arr2. If the found index is equal to the length of arr2, it means a - d is larger than any element in arr2, and thus also satisfies the condition.

Finally, we count and sum up all such a from arr1 that satisfy the condition by using the sum function on the generator expression that iterates through arr1 and applies the check function to each element.

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

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Solution Approach

The solution leverages binary search and sorting to efficiently determine if any elements in arr1 are within d distance of elements in arr2.

Here is a step-by-step explanation of the algorithm:

  1. Sorting arr2: The first step is to sort the array arr2. Sorting is important because it enables us to use binary search, which significantly reduces the time complexity of searching within arr2 from O(n) to O(log n) for each element in arr1.

  2. Defining a helper function check: Inside the Solution class, a helper function named check is defined which takes an integer a as input. The purpose of this function is to determine if there is an element in arr2 within d distance of a.

  3. Performing binary search with bisect_left: This function uses bisect_left from Python's bisect module. Given a sorted array and a target value, bisect_left returns the index where the target should be inserted to keep the array sorted. If we search for a - d in arr2, this will give us the lowest index i at which a - d could be inserted without violating the sorting order. This index i helps us quickly find the potential candidates in arr2 that could be within d distance from a.

  4. Checking the condition: The helper function then checks if the index i is at the end of arr2 (meaning that a is greater than all elements in arr2 plus d), or if the element at index i in arr2 is greater than a + d. If either of these conditions is true, it means that none of the elements in arr2 are within d distance of a. In this case, the function returns True.

  5. Counting elements with the sum function: Finally, in the findTheDistanceValue method, the sum function iterates over each element a in arr1 and applies the check function to it. This produces a generator of True or False values, where True indicates that a is at a valid distance from all elements in arr2. The sum function then adds up all the True values, which correspond to 1s, thus counting the elements in arr1 that satisfy the condition.

By utilizing a sorted array and binary search, the solution effectively reduces the number of comparisons that need to be made, resulting in an efficient algorithm with a lower time complexity suitable for large inputs.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let us illustrate the solution approach with a small example:

Suppose we have arr1 = [1, 4, 5, 7], arr2 = [3, 6, 10], and d = 2.

  1. Sorting arr2: First, we sort arr2, but it's already sorted in this case: arr2 = [3, 6, 10].

  2. Defining a helper function check: The check function will determine if arr1[i] is at least distance d apart from every element in arr2.

  3. Performing binary search with bisect_left:

    • For a = 1 from arr1: We find the place where 1 - 2 (which is -1) would fit in arr2 using bisect_left. The index returned is 0 because -1 is less than the first element in arr2. Since arr2[0] is 3, and 3 is greater than 1 + 2 (3 is not within the distance d from 1), the condition is satisfied.
    • For a = 4 from arr1: bisect_left of 4 - 2 will return index 1 because 2 fits between 3 and 6. However, the element at index 1 is 6, which is not greater than 4 + 2; therefore, the condition is not satisfied, and 4 is not at the required distance from an element in arr2.
    • For a = 5 from arr1: Using the same approach, the binary search returns index 2 (for 5 - 2), and arr2[2] is 10, which is greater than 5 + 2; hence, 5 is at a valid distance from all elements in arr2.
    • For a = 7 from arr1: The binary search for 7 - 2 returns index 2 as well, and since 10 is still greater than 7 + 2, 7 also satisfies the condition.

  4. Checking the condition: As explained above, after performing the binary search, the helper function checks the conditions to confirm if a is at the required distance from all elements in arr2.

  5. Counting elements with the sum function: We have found that elements 1, 5, and 7 from arr1 satisfy the condition of being at least distance d from all elements of arr2. Hence, our distance value would be the count of these elements, which is 3.

Following the approach above, the findTheDistanceValue method would return 3 for the given example, as there are three elements in arr1 that are at least distance d away from every element in arr2.

Solution Implementation

1from bisect import bisect_left
2from typing import List
3
4class Solution:
5    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
6        # Helper function to check if there's an element in arr2 within 
7        # the distance d of the element 'element_from_arr1'.
8        def is_valid(element_from_arr1: int) -> bool:
9            # Find the position in arr2 where 'element_from_arr1' - d could be inserted
10            # to maintain the sorted order.
11            index = bisect_left(arr2, element_from_arr1 - d)
12            # Return True if either:
13            # - index is at the end of arr2 (no element within distance d), or
14            # - the element at the found index is greater than 'element_from_arr1' + d
15            return index == len(arr2) or arr2[index] > element_from_arr1 + d
16
17        # Sort the second array to leverage binary searching.
18        arr2.sort()
19      
20        # Use list comprehension to iterate over arr1, applying 'is_valid'
21        # function to each element, and sum the results. The result will be
22        # the count of elements in arr1 that satisfy the distance value condition.
23        return sum(is_valid(element) for element in arr1)
24
1class Solution {
2  
3    // This function finds the distance value between two arrays.
4    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
5        // Sort the second array to perform binary search later.
6        Arrays.sort(arr2);
7      
8        // Initialize answer to count the number of elements meeting the condition.
9        int answer = 0;
10      
11        // Loop over each element in the first array.
12        for (int elemArr1 : arr1) {
13            // Check if the element in the first array meets the distance condition.
14            if (isDistanceMoreThanD(arr2, elemArr1, d)) {
15                // Increment the answer if the condition is met.
16                answer++;
17            }
18        }
19        // Return the number of elements that meet the condition.
20        return answer;
21    }
22
23    // Helper function to check if the distance between an element and all elements in another array is more than d.
24    private boolean isDistanceMoreThanD(int[] sortedArr2, int elemArr1, int d) {
25        int left = 0;
26        int right = sortedArr2.length;
27      
28        // Perform a binary search to find if there exists an element in arr2 that is within distance d of elemArr1.
29        while (left < right) {
30            int mid = left + (right - left) / 2; // Avoid potential overflow compared to (left + right) / 2.
31            if (sortedArr2[mid] >= elemArr1 - d) {
32                // If the middle element is within the lower bound of the distance, narrow the search to the left part.
33                right = mid;
34            } else {
35                // Otherwise, narrow the search to the right part.
36                left = mid + 1;
37            }
38        }
39      
40        // After the binary search, if the left index is out of bounds, it means all elements in arr2 are less than elemArr1 - d.
41        // If the left index points to an element, that element must be greater than elemArr1 + d to satisfy the condition.
42        return left >= sortedArr2.length || sortedArr2[left] > elemArr1 + d;
43    }
44}
45
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to calculate the distance value between two arrays
7    int findTheDistanceValue(std::vector<int>& arr1, std::vector<int>& arr2, int d) {
8        // Lambda function to check if no element in arr2 lies within the range [a - d, a + d]
9        // If true, a contributes to the distance value
10        auto isDistanceValid = [&](int a) -> bool {
11            // Finding the first element in arr2 which is not less than a - d
12            auto it = std::lower_bound(arr2.begin(), arr2.end(), a - d);
13            // Check if the iterator reached the end (no such element) or the found element is greater than a + d
14            return it == arr2.end() || *it > a + d;
15        };
16
17        // Sort array arr2 to use binary search (required by std::lower_bound)
18        std::sort(arr2.begin(), arr2.end());
19
20        // Initialize the distance value answer
21        int ans = 0;
22
23        // Iterate over each element in arr1
24        for (int a : arr1) {
25            // Increment the distance value answer if the element a satisfies the isDistanceValid condition
26            ans += isDistanceValid(a);
27        }
28
29        // Return the computed distance value
30        return ans;
31    }
32};
33
1function findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
2    // Helper function that checks if any element in arr2 is within d distance of element 'value'
3    const isElementDistanceValid = (value: number): boolean => {
4        let left = 0;
5        let right = arr2.length;
6        while (left < right) {
7            // Find the middle index
8            const middle = Math.floor((left + right) / 2);
9            // Check if the middle element is within the allowed distance
10            if (arr2[middle] >= value - d) {
11                right = middle; // Element is too close, adjust the search range to the left
12            } else {
13                left = middle + 1; // Element is not close enough, adjust the search range to the right
14            }
15        }
16        // If left is equal to length of arr2 or the element at 'left' index is outside the distance 'd' from 'value', return true
17        return left === arr2.length || arr2[left] > value + d;
18    };
19
20    // Sort the second array to enable binary search
21    arr2.sort((a, b) => a - b);
22    // Initialize the count of elements that satisfy the condition
23    let validElementCount = 0;
24    // Iterate through the elements of arr1
25    for (const value of arr1) {
26        // Check if the current element satisfies the distance condition for every element in arr2
27        if (isElementDistanceValid(value)) {
28            // If condition is met, increment the count
29            validElementCount++;
30        }
31    }
32    // Return the final count of valid elements
33    return validElementCount;
34}
35
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The given Python code defines a function findTheDistanceValue that computes the distance value between two lists arr1 and arr2, given a distance d. Here's an analysis of the time and space complexity:

Time Complexity:

  1. Sorting arr2 using arr2.sort(): The sort operation has a time complexity of O(n log n) where n is the length of arr2.
  2. Iterating through arr1 with the for loop: The loop runs m times where m is the length of arr1.
  3. The check function calls bisect_left, a binary search function, for every element a in arr1. The binary search runs in O(log n) time.
  4. Multiplying the above two factors, the for loop with the binary search operation results in a time complexity of O(m log n).

Adding both parts, the overall time complexity of the code is dominated by the O(m log n) part (since this part depends both on the length of arr1 and the fact that a binary search is performed on arr2), assuming m log n > n log n, which might be the case if m is significantly larger than n or vice versa. Therefore, the total time complexity is O(m log n).

Space Complexity:

  1. The sorted version of arr2: Python's sort() function sorts the list in place, so it doesn't use any additional space other than a small constant amount, hence it has a space complexity of O(1).
  2. The check function itself and the binary search do not use extra space that scales with the input size (they use a constant amount of extra space).

Therefore, the space complexity of the entire function is O(1) as there is no additional space used that depends on the input size of arr1 and arr2.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ