How does binary search optimize the 'Find the Distance Value Between Two Arrays' problem?

Binary search helps in finding the closest element in arr2 for each element in arr1 efficiently, reducing the time complexity from O(n*m) to O(nlogm).

Why is sorting arr2 necessary for solving this problem?

Sorting arr2 allows us to use binary search, which helps in quickly finding elements that meet the distance condition for each element in arr1.

What is the time complexity of the optimal solution for this problem?

The optimal solution has a time complexity of O(nlogm), where n is the length of arr1 and m is the length of arr2, due to sorting and binary search.

Can brute force be used to solve this problem?

Brute force can solve the problem, but it results in a time complexity of O(n*m), which is inefficient for larger arrays.

How can the solution be adapted for larger arrays?

For larger arrays, sorting arr2 and applying binary search ensures the solution remains efficient, scaling better with array sizes up to the problem's constraints.

#1385

Easy

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

两个数组间的距离值

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的距离值。「距离值」定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| 。示例 1：输入： arr1 = [4,5,8],…

数组双指针二分查找排序

题目描述

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。

「距离值」定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

示例 1：

输入：arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出：2
解释：
对于 arr1[0]=4 我们有：
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
所以 arr1[0]=4 符合距离要求

对于 arr1[1]=5 我们有：
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
所以 arr1[1]=5 也符合距离要求

对于 arr1[2]=8 我们有：
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2
存在距离小于等于 2 的情况，不符合距离要求 

故而只有 arr1[0]=4 和 arr1[1]=5 两个符合距离要求，距离值为 2

示例 2：

输入：arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
输出：2

示例 3：

输入：arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
输出：1

提示：

1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100

lightbulb

解题思路

方法一：排序 + 二分查找

我们可以先对数组 $\textit{arr2}$ 排序，然后对于数组 $\textit{arr1}$ 中的每个元素 $x$ ，使用二分查找，找到数组 $\textit{arr2}$ 中第一个大于等于 $x - d$ 的元素，如果元素存在，且小于等于 $x + d$ ，则说明不符合距离要求，否则说明符合距离要求。我们将符合距离要求的元素个数累加，即为答案。

时间复杂度 $O((m + n) \times \log n)$ ，空间复杂度 $O(\log n)$ 。其中 $m$ 和 $n$ 分别是数组 $\textit{arr1}$ 和 $\textit{arr2}$ 的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        arr2.sort()
        ans = 0
        for x in arr1:
            i = bisect_left(arr2, x - d)
            ans += i == len(arr2) or arr2[i] > x + d
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check for efficient use of binary search in handling the distance calculation for each element in arr1.
question_mark
Assess understanding of how sorting and binary search can optimize solutions for problems involving distance checks.
question_mark
Evaluate the candidate’s ability to correctly implement binary search over the answer space and handle edge cases with array lengths.

warning

常见陷阱

外企场景

error
Failing to sort arr2 before performing binary search will lead to incorrect results and inefficiency.
error
Incorrectly applying a brute force solution that results in O(n*m) time complexity, causing performance issues with larger inputs.
error
Misunderstanding the conditions for when the distance |arr1[i] - arr2[j]| is greater than or less than d, leading to incorrect counts.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the value of d to test how it affects the results and performance of the binary search.
arrow_right_alt
Use larger arrays to test the performance of the sorting and binary search approach.
arrow_right_alt
Modify the problem to allow arr1 and arr2 to contain non-unique values and test how the solution adapts.

help

常见问题

外企场景

继续练习

#1346 检查整数及其两倍数是否存在 #1498 满足条件的子序列数目 #1508 子数组和排序后的区间和