Get started

Find the Distance Value Between Two Arrays — Easy Problem & Solution

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.

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

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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue