Find the Distance Value Between Two Arrays

Find the Distance Value Between Two Arrays - 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.

In other words, count how many elements in arr1 are more than distance d away from all elements in arr2.

Input & Output

Example 1 — Basic Case

$ Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2

› Output: 2

💡 Note: For arr1[0]=4: closest in arr2 is 1, |4-1|=3 > 2 ✓. For arr1[1]=5: closest is 1, |5-1|=4 > 2 ✓. For arr1[2]=8: found 8 in arr2, |8-8|=0 ≤ 2 ✗. Result: 2 elements count.

Example 2 — All Elements Count

$ Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3

› Output: 4

💡 Note: All elements in arr1 are far enough from all elements in arr2. Minimum distances are all > 3, so all 4 elements count.

Example 3 — No Elements Count

$ Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6

› Output: 1

💡 Note: Only arr1[2]=100 is far enough from all arr2 elements. The others have at least one arr2 element within distance 6.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

arr1=[4,5,8], arr2=[10,9,1,8], d=2

Check Each Element

For each arr1[i], find if any arr2[j] satisfies |arr1[i]-arr2[j]| ≤ d

Count Valid

Count elements that are far from ALL arr2 elements

Key Takeaway

🎯 Key Insight: Each arr1 element must be far from its CLOSEST arr2 element to count

Asked in

f Facebook 15 M Microsoft 12 a Amazon 8

The key insight is that for each element in arr1, we need to check if ALL elements in arr2 are more than distance d away. Best approach uses sorting + binary search to efficiently find the closest elements. Time: O(m log m + n log m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×m)	O(1)	For each element in arr1, check against all elements in arr2
Sort Then Search	O(m log m + n log m)	O(1)	Sort arr2 first, then use binary search for each arr1 element

Brute Force — Algorithm Steps

For each element arr1[i]
Check all elements arr2[j]
If |arr1[i] - arr2[j]| <= d for any j, skip this element
Otherwise increment count

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Element

Take first element from arr1

Check All

Compare against every element in arr2

Count Valid

If no element is within distance d, increment counter

Code -

solution.c — C

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

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

int main() {
    char line[1000];
    int arr1[100], arr2[100];
    int arr1Size = 0, arr2Size = 0, d;
    
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr1[arr1Size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr2[arr2Size++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    scanf("%d", &d);
    
    printf("%d\n", solution(arr1, arr1Size, arr2, arr2Size, d));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each of n elements in arr1, we check all m elements in arr2

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables, no extra data structures

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler