Skip to main content
Talentd

Find the Distance Value Between Two Arrays - Solution & Explanation

EasyArrayTwo PointersBinary SearchSorting17 min readAsked at: Microsoft, Uber, Google +2
Practice this problem

Problem Statement

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

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
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=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

 

Constraints:

  • 1 <= arr1.length, arr2.length <= 500
  • -1000 <= arr1[i], arr2[j] <= 1000
  • 0 <= d <= 100

Approach Overview

Problem Overview: You are given two integer arrays arr1 and arr2 and an integer d. The task is to count how many elements in arr1 have a distance greater than d from every element in arr2. In other words, for each value x in arr1, check that |x - y| > d for all values y in arr2. If that condition holds, the element contributes to the final count.

Approach 1: Brute Force Comparison (O(n * m) time, O(1) space)

The most direct method is to compare every element in arr1 with every element in arr2. For each arr1[i], iterate through arr2 and compute the absolute difference |arr1[i] - arr2[j]|. If any difference is less than or equal to d, the element is invalid and you stop checking further for that value. Otherwise, it contributes to the distance value. This approach relies purely on nested iteration over the array elements. It is easy to implement and works well when both arrays are small, but the quadratic comparison cost becomes expensive as input sizes grow.

Approach 2: Sorting + Binary Search (O(m log m + n log m) time, O(1) extra space)

A more efficient strategy is to first sort arr2. Once sorted, you can use binary search to quickly locate the closest element in arr2 for each value in arr1. For a given x, perform a binary search to find the insertion position in arr2. Then check the neighboring elements around that position to determine the smallest possible distance. If both neighbors have an absolute difference greater than d, the element qualifies. Sorting enables logarithmic lookups instead of scanning the entire array. The preprocessing cost is O(m log m) for sorting, and each query takes O(log m), producing a total runtime of O(m log m + n log m). This pattern often appears in problems combining sorting with fast lookups.

Recommended for interviews: Interviewers expect the sorting + binary search approach. The brute force solution demonstrates you understand the definition of the distance constraint and can implement the logic correctly. The optimized approach shows stronger algorithmic thinking by reducing repeated comparisons using ordering and logarithmic search. When arrays grow large, the difference between O(n * m) and O(n log m) becomes significant, which is exactly the optimization interviewers want to see.

Approach 1: Brute Force Approach

This approach involves iterating over each element in arr1 and checking the absolute differences with each element in arr2. If none of the elements in arr2 are within a distance d, we increase the count. This approach uses nested loops resulting in a time complexity of O(n*m).

This solution iterates through each element of arr1 and checks against all elements of arr2. If |arr1[i] - arr2[j]| > d for all j, it increments a counter.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), where n and m are the sizes of arr1 and arr2 respectively.
Space Complexity: O(1), since we are using only a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Optimized Approach with Sorting and Binary Search

This approach first sorts arr2 and then uses binary search to quickly determine if there exists any element in arr2 within the distance d from any element in arr1. This significantly reduces the time complexity compared to the brute force approach.

This solution first sorts arr2. For each element in arr1, it performs a binary search in arr2 to check if there's an element that satisfies the condition. The sorting enables use of binary search to improve efficiency.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m log m + n log m), where m is the size of arr2 due to sorting and binary searching, and n is the size of arr1.
Space Complexity: O(1), ignoring the space required for sorting.

Try this approach in the editor →

Approach 3: Sorting + Binary Search

We can first sort the array arr2, and then for each element x in the array arr1, use binary search to find the first element in the array arr2 that is greater than or equal to x - d. If such an element exists and is less than or equal to x + d, it does not meet the distance requirement. Otherwise, it meets the distance requirement. We count the number of elements that meet the distance requirement, which is the answer.

The time complexity is O((m + n) times log n), and the space complexity is O(log n). Here, m and n are the lengths of the arrays arr1 and arr2, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n*m), where n and m are the sizes of arr1 and arr2 respectively.
Space Complexity: O(1), since we are using only a fixed amount of extra space.

Optimized Approach with Sorting and Binary Search

Time Complexity: O(m log m + n log m), where m is the size of arr2 due to sorting and binary searching, and n is the size of arr1.
Space Complexity: O(1), ignoring the space required for sorting.

Sorting + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ComparisonO(n * m)O(1)Good for understanding the problem or when both arrays are very small
Sorting + Binary SearchO(m log m + n log m)O(1)Preferred for interviews and large inputs where scanning arr2 repeatedly is too slow

Video Solution

Leetcode 1385. Find the Distance Value Between Two Arrays (Easy) • onepunchcoder • 5,711 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Distance Value Between Two Arrays easy or hard?
The problem is classified as Easy on LeetCode with an acceptance rate above 70%. The brute force logic is straightforward, but recognizing that sorting arr2 enables faster binary searches is the key optimization that improves performance.
Find the Distance Value Between Two Arrays Python/Java solution
In Python or Java, the optimized solution sorts arr2 and uses built-in binary search utilities such as bisect in Python or Arrays.binarySearch in Java. After locating the insertion index, you check adjacent elements to confirm the distance constraint before counting the element.
How to solve Find the Distance Value Between Two Arrays in O(n log m)?
First sort arr2. For each element x in arr1, run a binary search to find the closest position in arr2 where x could be inserted. Check the neighbor values around that index and compute the absolute difference. If both neighbors differ from x by more than d, count the element.
What is the best approach for Find the Distance Value Between Two Arrays?
The most efficient approach sorts arr2 and then performs binary search for each element in arr1. After sorting, you locate the closest value in arr2 and check whether the absolute difference is greater than d. This reduces repeated comparisons and runs in O(m log m + n log m) time with constant extra space.
Is Find the Distance Value Between Two Arrays asked at Google/Amazon/Meta?
Problems combining arrays with binary search patterns frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear verbatim, the technique of sorting one array and searching for closest values is a common interview pattern.
What data structure is used in Find the Distance Value Between Two Arrays?
The problem mainly uses arrays along with algorithmic techniques like sorting and binary search. No advanced data structures are required. The key idea is leveraging the sorted order of arr2 to quickly find the nearest values for comparison.
What is the time complexity of Find the Distance Value Between Two Arrays?
The brute force solution takes O(n * m) time because every element in arr1 is compared with every element in arr2. The optimized approach sorts arr2 in O(m log m) and then performs binary search for each element of arr1 in O(log m), giving a total time complexity of O(m log m + n log m).

Ready to solve this problem?

Practice Find the Distance Value Between Two Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays