Find the Distance Value Between Two Arrays

Easy
750.

Find the Distance Value Between Two Arrays

Find the Distance Value Between Two Arrays is an easy coding problem on arrays, binary search and two pointers, asked in Amazon, TCS and Wipro interviews.

The distance value is the number of elements a in arr1 for which there is no element b in arr2 with |a - b| <= d.

Return the distance value.

Example 1

Input
arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output
2
Explanation
Only 8 has a neighbour within 2 (namely 8 and 9).

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr1
 * @param {number[]} arr2
 * @param {number} d
 * @return {number}
 */
var findTheDistanceValue = function(arr1, arr2, d) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Distance Value Between Two Arrays — Solution

Find the Distance Value Between Two Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Distance Value Between Two Arrays is an easy coding problem on arrays, binary search and two pointers, asked in Amazon, TCS and Wipro interviews.

Problem statement

The distance value is the number of elements a in arr1 for which there is no element b in arr2 with |a - b| <= d.

Return the distance value.

Example 1

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: Only 8 has a neighbour within 2 (namely 8 and 9).

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

Hints for Find the Distance Value Between Two Arrays

  1. Hint 1

    The direct double loop is O(n·m) and fine at these sizes.

  2. Hint 2

    The faster route sorts arr2 and binary searches for the nearest value to each a.

  3. Hint 3

    Only the closest element on each side can violate the condition.

How to solve Find the Distance Value Between Two Arrays

An element of arr1 survives when the whole of arr2 stays strictly further than d away from it. Checking that directly is a nested scan; sorting arr2 lets a binary search test only the two nearest candidates.

Approach

  1. For each a in arr1, scan arr2 for any b with |a - b| <= d.
  2. Count a when no such b exists.
  3. To speed it up: sort arr2, binary search for a, and test only the neighbour on each side.

Why it works

If any element of arr2 lies within d of a, the closest one does — so testing the immediate predecessor and successor in sorted order is exhaustive.

Complexity

  • Time — O(n · m), or O((n + m) log m) with sorting
  • Space — O(1)

Pitfalls

  • <= d is inclusive, so a difference of exactly d disqualifies the element.
  • Counting elements of arr2 rather than arr1 answers the mirror question.
  • Negative values mean the absolute difference is essential.

Reference solution

Python

from typing import List

def findTheDistanceValue(arr1: List[int], arr2: List[int], d: int) -> int:
    return sum(1 for a in arr1 if all(abs(a - b) > d for b in arr2))

Java

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

C++

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

JavaScript

var findTheDistanceValue = function(arr1, arr2, d) {
    var total = 0;
    for (var i = 0; i < arr1.length; i++) {
        var ok = true;
        for (var j = 0; j < arr2.length; j++) {
            if (Math.abs(arr1[i] - arr2[j]) <= d) { ok = false; break; }
        }
        if (ok) total++;
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search