1385. Find Distance Value Between Two Arrays

The problem

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).

Python

def find_the_distance_value(arr1, arr2, d):
    count = 0
    for a in arr1:
        if all(abs(a - b) > d for b in arr2):
            count += 1
    return count

arr1 = [4, 5, 8]
arr2 = [10, 9, 1, 8]
d = 2
print(find_the_distance_value(arr1, arr2, d))

Java

public class DistanceValue {
    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int count = 0;
        for (int a : arr1) {
            boolean valid = true;
            for (int b : arr2) {
                if (Math.abs(a - b) <= d) {
                    valid = false;
                    break;
                }
            }
            if (valid) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr1 = {4, 5, 8};
        int[] arr2 = {10, 9, 1, 8};
        int d = 2;
        System.out.println(findTheDistanceValue(arr1, arr2, d));
    }
}

C++

#include <iostream>
#include <vector>
#include <cmath>

int findTheDistanceValue(std::vector<int>& arr1, std::vector<int>& arr2, int d) {
    int count = 0;
    for (int a : arr1) {
        bool valid = true;
        for (int b : arr2) {
            if (std::abs(a - b) <= d) {
                valid = false;
                break;
            }
        }
        if (valid) count++;
    }
    return count;
}

int main() {
    std::vector<int> arr1 = {4, 5, 8};
    std::vector<int> arr2 = {10, 9, 1, 8};
    int d = 2;
    std::cout << findTheDistanceValue(arr1, arr2, d) << std::endl;
    return 0;
}

JavaScript

function findTheDistanceValue(arr1, arr2, d) {
    let count = 0;
    for (let a of arr1) {
        if (arr2.every(b => Math.abs(a - b) > d)) {
            count++;
        }
    }
    return count;
}

const arr1 = [4, 5, 8];
const arr2 = [10, 9, 1, 8];
const d = 2;
console.log(findTheDistanceValue(arr1, arr2, d));

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d) {
    int count = 0;
    for (int i = 0; i < arr1Size; i++) {
        int valid = 1;
        for (int j = 0; j < arr2Size; j++) {
            if (abs(arr1[i] - arr2[j]) <= d) {
                valid = 0;
                break;
            }
        }
        if (valid) count++;
    }
    return count;
}

int main() {
    int arr1[] = {4, 5, 8};
    int arr2[] = {10, 9, 1, 8};
    int d = 2;
    int result = findTheDistanceValue(arr1, 3, arr2, 4, d);
    printf("%d\n", result);
    return 0;
}

using System;

public class DistanceValue {
    public static int FindTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int count = 0;
        foreach (int a in arr1) {
            bool valid = true;
            foreach (int b in arr2) {
                if (Math.Abs(a - b) <= d) {
                    valid = false;
                    break;
                }
            }
            if (valid) count++;
        }
        return count;
    }

    public static void Main() {
        int[] arr1 = { 4, 5, 8 };
        int[] arr2 = { 10, 9, 1, 8 };
        int d = 2;
        Console.WriteLine(FindTheDistanceValue(arr1, arr2, d));
    }
}

In Python, the solution uses list comprehensions to evaluate the condition all(abs(a - b) > d for b in arr2) in a concise manner.

Complexity

Time Complexity: O(n*m)
Space Complexity: O(1)

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.

Python

def find_the_distance_value(arr1, arr2, d):
    arr2.sort()
    count = 0
    for a in arr1:
        left, right = 0, len(arr2) - 1
        valid = True
        while left <= right:
            mid = (left + right) // 2
            if abs(arr2[mid] - a) <= d:
                valid = False
                break
            if arr2[mid] < a:
                left = mid + 1
            else:
                right = mid - 1
        if valid:
            count += 1
    return count

arr1 = [4, 5, 8]
arr2 = [10, 9, 1, 8]
d = 2
print(find_the_distance_value(arr1, arr2, d))

Java

import java.util.Arrays;

public class DistanceValue {
    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int count = 0;
        for (int a : arr1) {
            int left = 0, right = arr2.length - 1;
            boolean valid = true;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (Math.abs(arr2[mid] - a) <= d) {
                    valid = false;
                    break;
                }
                if (arr2[mid] < a) left = mid + 1;
                else right = mid - 1;
            }
            if (valid) count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[] arr1 = {4, 5, 8};
        int[] arr2 = {10, 9, 1, 8};
        int d = 2;
        System.out.println(findTheDistanceValue(arr1, arr2, d));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int findTheDistanceValue(std::vector<int>& arr1, std::vector<int>& arr2, int d) {
    std::sort(arr2.begin(), arr2.end());
    int count = 0;
    for (int a : arr1) {
        if (std::none_of(arr2.begin(), arr2.end(), [a, d](int b) { return std::abs(a - b) <= d; })) {
            count++;
        }
    }
    return count;
}

int main() {
    std::vector<int> arr1 = {4, 5, 8};
    std::vector<int> arr2 = {10, 9, 1, 8};
    int d = 2;
    std::cout << findTheDistanceValue(arr1, arr2, d) << std::endl;
    return 0;
}

JavaScript

function findTheDistanceValue(arr1, arr2, d) {
    arr2.sort((a, b) => a - b);

    const binarySearch = (target) => {
        let left = 0, right = arr2.length - 1;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (Math.abs(arr2[mid] - target) <= d) {
                return true;
            }
            if (arr2[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    };

    let count = 0;
    for (let a of arr1) {
        if (!binarySearch(a)) {
            count++;
        }
    }
    return count;
}

const arr1 = [4, 5, 8];
const arr2 = [10, 9, 1, 8];
const d = 2;
console.log(findTheDistanceValue(arr1, arr2, d));

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int *arr, int size, int target, int d) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (abs(arr[mid] - target) <= d) return 1;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return 0;
}

int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d) {
    qsort(arr2, arr2Size, sizeof(int), compare);
    int count = 0;
    for (int i = 0; i < arr1Size; i++) {
        if (!binarySearch(arr2, arr2Size, arr1[i], d)) {
            count++;
        }
    }
    return count;
}

int main() {
    int arr1[] = {4, 5, 8};
    int arr2[] = {10, 9, 1, 8};
    int d = 2;
    int result = findTheDistanceValue(arr1, 3, arr2, 4, d);
    printf("%d\n", result);
    return 0;
}

using System;

public class DistanceValue {
    public static int FindTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Array.Sort(arr2);
        int count = 0;
        foreach (int a in arr1) {
            int left = 0, right = arr2.Length - 1;
            bool valid = true;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (Math.Abs(arr2[mid] - a) <= d) {
                    valid = false;
                    break;
                }
                if (arr2[mid] < a) left = mid + 1;
                else right = mid - 1;
            }
            if (valid) count++;
        }
        return count;
    }

    public static void Main() {
        int[] arr1 = { 4, 5, 8 };
        int[] arr2 = { 10, 9, 1, 8 };
        int d = 2;
        Console.WriteLine(FindTheDistanceValue(arr1, arr2, d));
    }
}

In this Python solution, arr2 is sorted and a binary search is performed for each element of arr1. The binary search efficiently determines if any element in arr2 violates the distance condition.

Complexity

Time Complexity: O(m log m + n log m)
Space Complexity: O(1)

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.

TypeScript

function findTheDistanceValue(arr1: number[], arr2: number[], d: number): number {
    arr2.sort((a, b) => a - b);
    let ans: number = 0;
    for (const x of arr1) {
        const i = _.sortedIndex(arr2, x - d);
        if (i === arr2.length || arr2[i] > x + d) {
            ++ans;
        }
    }
    return ans;
}

func findTheDistanceValue(arr1 []int, arr2 []int, d int) (ans int) {
	sort.Ints(arr2)
	for _, x := range arr1 {
		i := sort.SearchInts(arr2, x-d)
		if i == len(arr2) || arr2[i] > x+d {
			ans++
		}
	}
	return
}

Rust

impl Solution {
    pub fn find_the_distance_value(arr1: Vec<i32>, mut arr2: Vec<i32>, d: i32) -> i32 {
        arr2.sort();
        let mut ans = 0;
        for &x in &arr1 {
            let i = match arr2.binary_search(&(x - d)) {
                Ok(j) => j,
                Err(j) => j,
            };
            if i == arr2.len() || arr2[i] > x + d {
                ans += 1;
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n*m) Space Complexity: O(1)
Optimized Approach with Sorting and Binary Search	Time Complexity: O(m log m + n log m) Space Complexity: O(1)
Sorting + Binary Search	–

Complexity analysis

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

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).

Find the Distance Value Between Two Arrays solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach with Sorting and Binary Search

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Distance Value Between Two Arrays solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach with Sorting and Binary Search

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems