Skip to main content

Binary Search

Find the Distance Value Between Two Arrays Solution In C++/Java/Python/JS

Problem Description:

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

Examples:

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

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2
Explanation: values 1 and 2 from arr1 are the only elements with distances from values of arr2 > d=3

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1
Explanation: value 100 from arr1 is the only element with distances from values of arr2 > d=6

Constraints:

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

Brute Force Approach

Intuition:

The problem asks us to find the distance value between two integer arrays, arr1 and arr2, with a given integer d.

The distance value is the number of elements in arr1 such that the absolute difference between that element and every element in arr2 is more significant than d.

What can we infer from this?

If we say that the absolute difference between arr1[i] and any arr2[j] is less than or equal to d, then that element of arr1 becomes "bad" and won’t be counted in the result. This means that for every value of arr1[i] where i is from 0 to arr1.size -1, there shouldn’t be any arr2[j] such that the distance between them is <= d. In this case we arr1[i] become “Good”

💡
Try it Yourself !

The brute force in this case would simply mean checking every pair of elements between arr1 and arr2 counting those which are “good”.

To solve this, we first initialise a counter to keep track of "good" elements. Then, we go through each element in arr1 one by one.

For each element in arr1, we compare it with every element in arr2. If we find that the absolute difference is less than or equal to d, we stop checking further and mark it as "bad".

If we finish checking all elements in arr2 without finding any conflict, the element is considered "good" and we increase the counter by 1.

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

  • First element = 4
    • Differences with arr2 = [6, 5, 3, 4] → All greater than 2 → "Good" → Increase count.
  • Second element = 5
    • Differences with arr2 = [5, 4, 4, 3] → All greater than 2 → "Good" → Increase count.
  • Third element = 8
    • Differences with arr2 = [2, 1, 7, 0] → 2 is equal to d → "Bad" → No increase in count.

Finally, the count of "good" elements is 2.

The key idea is that if we find even a single pair where the difference is less than or equal to d, the element becomes "bad" immediately. This allows us to skip further checks, improving efficiency.

Illustration of Find the Distance Value Between Two Arrays Brute Force Approach 1
Illustration of Find the Distance Value Between Two Arrays Brute Force Approach 2

Find the Distance Value Between Two Arrays Example

Input: arr1 = [2, 5, 15], arr2 = [-3, 5, 10], d = 3
Output: 1F
Explanation: value 15 from arr1 is the only element with distances from values of arr2 > d=3

Initialize Variables

  1. n = arr1.size() = 3 (since arr1 has 3 elements)
  2. m = arr2.size() = 3 (since arr2 has 3 elements)
  3. ans = 0 (to keep track of valid distance values)

Outer Loop Starts

We will now iterate through each element of arr1 using the outer loop.

First Outer Loop Iteration (i = 0)

  1. Current element in arr1 = arr1[0] = 2
  2. Start inner loop:
    • j = 0
      • Compare |2 - (-3)| = 5
      • Since 5 > d, continue to next value
    • j = 1
      • Compare |2 - 5| = 3
      • Since 3 <= d, break the loop
  4. Since the inner loop broke early, we do not increment ans

Second Outer Loop Iteration (i = 1)

  1. Current element in arr1 = arr1[1] = 5
  2. Start inner loop:
    • j = 0
      • Compare |5 - (-3)| = 8
      • Since 8 > d, continue to next value
    • j = 1
      • Compare |5 - 5| = 0
      • Since 0 <= d, break the loop
  4. Since the inner loop broke early, we do not increment ans

Step 5: Third Outer Loop Iteration (i = 2)

  1. Current element in arr1 = arr1[2] = 15
  2. Start inner loop:
    • j = 0
      • Compare |15 - (-3)| = 18
      • Since 18 > d, continue to next value
    • j = 1
      • Compare |15 - 5| = 10
      • Since 10 > d, continue to next value
    • j = 2
      • Compare |15 - 10| = 5
      • Since 5 > d, continue to next value
  4. The inner loop finishes without breaking, which means all values in arr2 are at a distance greater than d from 15. Therefore, increment ans → ans = 1

Step 6: Final Result

  • Only 15 in arr1 satisfies the condition of being at a distance greater than d from all elements of arr2.
  • Therefore, ans = 1.

Step 7: Return the Answer

  • return ans → 1

Find the Distance Value Between Two Arrays Algorithm

Step 1: Initialize variables

  • Get the sizes of arr1 and arr2.
  • Create a variable ans to store the final count of valid values from arr1.

Step 2: Iterate through each element of arr1

  • Use a loop to go through each element of arr1.

Step 3: Check distance with elements of arr2

  • Use another loop to compare the current element of arr1 with each element of arr2.
  • If the absolute difference between the two elements is <= d, break the loop because the value is invalid.

Step 4: Update the answer

  • If the inner loop completes without finding any value that satisfies abs(arr1[i] - arr2[j]) <= d, it means arr1[i] is a valid value.
  • Increase the answer count.

Step 5: Return the result

  • After checking all values of arr1, return the final answer count.

Find the Distance Value Between Two Arrays Solution
Find the Distance Value Between Two Arrays Solution in C++ 
class Solution {
public:
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
		// Size of arr1
        int n = arr1.size(); 
		// Size of arr2
        int m = arr2.size(); 

		// Counter for valid distance values
        int ans = 0; 

        // Step 1: Iterate over each element in arr1
        for (int i = 0; i < n; ++i) {
            int j;

            // Step 2: Compare the current element in arr1 with each element in arr2
            for (j = 0; j < m; ++j) {
                // Step 3: If the absolute difference is within the threshold, stop checking
                if (abs(arr1[i] - arr2[j]) <= d) {
                    break;
                }
            }

            // Step 4: If we checked all elements and found no close value, increment count
            if (j == m) {
                ans++;
            }
        }

        // Step 5: Return the result
        return ans;
    }
};

Find the Distance Value Between Two Arrays Solution in Java 
class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int n = arr1.length; // Size of arr1
        int m = arr2.length; // Size of arr2

        int ans = 0; // Counter for valid distance values

        // Step 1: Iterate over each element in arr1
        for (int i = 0; i < n; ++i) {
            int j;

            // Step 2: Compare the current element in arr1 with each element in arr2
            for (j = 0; j < m; ++j) {
                // Step 3: If the absolute difference is within the threshold, stop checking
                if (Math.abs(arr1[i] - arr2[j]) <= d) {
                    break;
                }
            }

            // Step 4: If we checked all elements and found no close value, increment count
            if (j == m) {
                ans++;
            }
        }

        // Step 5: Return the result
        return ans;
    }
}

Find the Distance Value Between Two Arrays Solution in Python 
class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        n = len(arr1) # Size of arr1
        m = len(arr2) # Size of arr2

        ans = 0 # Counter for valid distance values

        # Step 1: Iterate over each element in arr1
        for num in arr1:
            is_valid = True

            # Step 2: Compare with each element in arr2
            for x in arr2:
                # Step 3: If the absolute difference is within the threshold, mark as invalid
                if abs(num - x) <= d:
                    is_valid = False
                    break
            
            # Step 4: If no close value found, increment the counter
            if is_valid:
                ans += 1
        
        # Step 5: Return the result
        return ans

Find the Distance Value Between Two Arrays Solution in Javascript 
Javascript/**
 * @param {number[]} arr1 - First input array
 * @param {number[]} arr2 - Second input array
 * @param {number} d - Distance value threshold
 * @return {number} - Number of valid distance values
 */
var findTheDistanceValue = function(arr1, arr2, d) {
    let ans = 0; // Counter for valid distance values

    // Step 1: Iterate over each element in arr1
    for (let num of arr1) {
        let isValid = true;

        // Step 2: Compare with each element in arr2
        for (let x of arr2) {
            // Step 3: If absolute difference is within threshold, mark as invalid
            if (Math.abs(num - x) <= d) {
                isValid = false;
                break;
            }
        }

        // Step 4: If no close value found, increment the counter
        if (isValid) {
            ans++;
        }
    }

    // Step 5: Return the result
    return ans;
};

Find the Distance Value Between Two Arrays Complexity Analysis

Time Complexity: O(n×m)

To analyze the time complexity of the code, let's break down the operations step-by-step:

1. Outer Loop Complexity

  • The outer loop iterates through all elements of arr1.
  • If the size of arr1 is n, the loop will run n times.
  • Outer Loop Complexity=O(n)

2. Inner Loop Complexity

  • For each element in arr1, the inner loop iterates through all elements of arr2.
  • If the size of arr2 is m, the inner loop will run m times in the worst case.
  • The abs() function and the comparison operation inside the loop are constant-time operations, i.e., O(1).
  • Therefore, the inner loop takes O(m) time in the worst case.
  • Inner Loop Complexity=O(m)

3. Break Condition Effect

  • The break condition if(abs(arr1[i] - arr2[j]) <= d) allows the inner loop to terminate early.
  • However, in the worst-case scenario, the break condition might never be satisfied, meaning the loop would run for all m elements of arr2.
  • Therefore, the inner loop complexity remains O(m) in the worst case.

Since the outer loop runs n times and the inner loop runs at most m times for each iteration, the total time complexity becomes: O(n×m)

Space Complexity: O(1)

To analyze the space complexity, let’s break it down step-by-step:

1. Auxiliary Space Complexity

Auxiliary space refers to the extra space used by the algorithm excluding input size. Let's go through the components of the code:

  • Variables:
    • n, m, ans, and i, j are integer variables.
    • Total space used by integer variables = O(1)
  • Function Call Stack:
    • No recursion is used, so no extra stack space is needed.
    • Space used = O(1)
  • Intermediate Computations:
    • abs() function and comparisons are constant-time operations that don’t require extra space.
    • Space used = O(1)
    • Auxiliary Space Complexity = O(1)

2. Total Space Complexity

Input Space Complexity: Input space refers to the space used by the input arrays arr1 and arr2.

  • arr1 and arr2 are passed as input, so their sizes contribute to the overall space complexity.
  • If n = arr1.size() and m = arr2.size(), the space used is: O(n+m)

The total space complexity includes both auxiliary space and input space: O(n+m)+O(1) = O(n+m)

Is the brute force efficient ?

For n, m ≤ 500, our solution has a time complexity of O(n×m), which will comfortably meet the given constraints.

In such environments, it is common for problems to handle up to 10⁶ operations within these limits.

Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning your solution should be able to handle this number of operations within the time limits. When multiple test cases are involved, the total number of operations can go up to 10⁸.

Optimal Approach

Intuition:

Currently, the complexity of the brute force solution is O(n×m) due to the nested loops used to operate on every pair of values in arr1 and arr2.

Now, let's think about how we can reduce the time complexity. Clearly, the loops are the major contributors to the time complexity, so we need to optimise them.

Let's start with the outer loop. We see that the loop iterates over all the values of arr1. For each value, there are only two possible outcomes — either the value will contribute to the answer, or it won’t. Therefore, we cannot change this loop since we need to check every element in arr1.

Now, let’s analyse the inner loop. This loop iterates over the values of arr2, and as soon as we find that the distance between arr1[i] and arr2[j] is <= d, we break the loop.

Now, forget about d for a moment and think about finding a value in arr2 such that the distance between that value and arr1[i] is as small as possible.

If we can somehow find a value in arr2 such that the distance between arr1[i] and that value is the minimum possible, then we only need to check a single condition.

If the minimum distance is <= d, then arr1[i] is "bad" and won’t contribute to the answer. Otherwise, we can increase the answer count. That makes sense, right...?

But why does finding the minimum possible distance work?

If the smallest distance between arr1[i] and any element in arr2 is greater than d, then it means that all other distances (which will be greater than this minimum) will also be greater than d.

Therefore, if the smallest distance is greater than d, we are guaranteed that none of the distances between arr1[i] and elements in arr2 will be <= d. That's why focusing on the minimum distance helps us decide the outcome in one step rather than comparing it with all values in arr2.

This is the key intuition behind the optimised approach. The only thing left is figuring out how to efficiently find the closest value in arr2 to arr1[i].

How do you efficiently find the closest value in arr2 to arr1[i]?

To efficiently find the closest value in arr2 to arr1[i], let's first think about how sorting arr2 can help us.

If arr2 is sorted, the values will be in increasing order. This means that for any value arr1[i], the closest value in arr2 will either be directly to the left or to the right of where arr1[i] would be if it were inserted into arr2.

This is because once the array is sorted, the values are arranged in a structured way — smaller values on the left and larger values on the right. Therefore, the closest value will always be the element just smaller than arr1[i] or the element just larger than arr1[i].

How can we quickly find this position?

To find the closest value in arr2 to arr1[i], let's carefully understand how to search efficiently using the middle element.

Instead of checking each element one by one, we can pick the middle element of arr2 and compare it with arr1[i]. This gives us valuable information about which side of the array we should search next. 

Assume the middle element of arr2 is mid. Once we get our mid we can compare it with arr1[i] and make a choice to move left of mid or right of mid.

What cases should we consider when comparing the middle element with arr1[i]?

Case 1: If the middle element is exactly equal to arr1[i]:

If arr2[mid] == arr1[i], then the distance is zero, which is the smallest possible distance. In this case, we have already found the closest element, so we can stop searching immediately.

Example: arr1=[5], arr2=[1,3,5,7,9]

For arr1[i] = 5:

  • Mid element of arr2 = arr2[2] = 5 (which is equal to arr1[i]).
  • Since the distance is zero, we stop searching because this is the closest element.
Illustration of Find the Distance Value Between Two Arrays Optimal Case 1

Case 2: If the middle element is smaller than arr1[i]:

If arr2[mid] < arr1[i], this means that the closest element could either be this or on the further right side of the array, since larger values might be closer. Therefore, we can check if arr2[mid] can safely ignore the left half and search in the right half of the array.

Example: arr1=[6],arr2=[1,3,5,7,9]

For arr1[i] = 6:

  • Mid element = arr2[2] = 5 (less than 6).
  • Distance = |6 - 5| = 1
  • We check if this distance is smaller than the current distance, if yes, then we mark this distance as the current distance.
  • Then move to the right half since larger values might be closer to 6.
Illustration of Find the Distance Value Between Two Arrays Optimal Case 2

Case 3: If the middle element is larger than arr1[i]:

If arr2[mid] > arr1[i], this means that the closest element could either be this or on the further left side of the array, since smaller values might be closer. Therefore, we can check if arr2[mid] can be our answer and simply ignore the right half and continue searching in the left half of the array.

Example: arr1=[4], arr2=[1,3,5,7,9]

For arr1[i] = 6:

  • Mid element = arr2[2] = 5 (greater than 6).
  • Distance = |4 - 5| = 1
  • We check if this distance is smaller than the current distance; if yes, then we mark this distance as the current distance.
  • Then move to the left half since smaller values might be closer to 4.
Illustration of Find the Distance Value Between Two Arrays Optimal Case 3

How does this reduce the search space?

Each time we make a comparison and move to the left or right half, we are cutting the search space in half. This means that after each step, the size of the problem is reduced by half, which searches much faster. 

This algorithm, which we just used, is called binary search. This reduction in search space is the core reason why binary search has a time complexity of O(log m).

By repeating this process, we eventually narrow down to the closest possible element or the two neighbouring elements — one smaller and one larger — that we need to check to compute the minimum distance.

This is how binary search helps us quickly find the closest value in a sorted array.

💡
Binary Search in detail !
0:00
/1:21

Animation of Find the Distance Value Between Two Arrays Optimal Approach

Find the Distance Value Between Two Arrays Example

Input: arr1 = [2, 5, 15], arr2 = [-3, 5, 10], d = 3
Output: 1
Explanation: value 15 from arr1 is the only element with distances from values of arr2 > d=3

Step 1: Initialize Variables

  1. n = arr1.size() = 3 (since arr1 has 3 elements)
  2. m = arr2.size() = 3 (since arr2 has 3 elements)
  3. ans = 0 (to keep track of valid distance values)

Step 2: Sort arr2

We sort arr2 to apply binary search: [−3,5,10]

]Step 3: Outer Loop Starts

We will now iterate through each element of arr1 using the outer loop.

Step 4: First Outer Loop Iteration (i = 0)

  1. Current element in arr1 = arr1[0] = 2
  2. Initialize binary search variables: low = 0, high = 2, index = 0

Binary Search Steps:

  • Step 1:
    • mid = (0 + 2) / 2 = 1
    • arr2[mid] = 5
    • Since 2 < 5, update index = 1 and search left side → high = 0
  • Step 2:
    • mid = (0 + 0) / 2 = 0
    • arr2[mid] = -3
    • Since 2 > -3, update index = 0 and search right side → low = 1
  • Binary search ends. The closest element is at index = 1 → arr2[1] = 5

Check the Condition:

  • |2 - 5| = 3
  • Since 3 <= d, do not increment ans

Step 5: Second Outer Loop Iteration (i = 1)

  1. Current element in arr1 = arr1[1] = 5
  2. Initialize binary search variables: low = 0, high = 2, index = 0

Binary Search Steps:

  • Step 1:
    • mid = (0 + 2) / 2 = 1
    • arr2[mid] = 5
    • Since 5 == 5, set index = 1 and break
  • Binary search ends. The closest element is at index = 1 → arr2[1] = 5

Check the Condition:

  • |5 - 5| = 0
  • Since 0 <= d, do not increment ans

Step 6: Third Outer Loop Iteration (i = 2)

  1. Current element in arr1 = arr1[2] = 15
  2. Initialize binary search variables: low = 0, high = 2, index = 0

Binary Search Steps:

  • Step 1:
    • mid = (0 + 2) / 2 = 1
    • arr2[mid] = 5
    • Since 15 > 5, update index = 1 and search the right side → low = 2
  • Step 2:
    • mid = (2 + 2) / 2 = 2
    • arr2[mid] = 10
    • Since 15 > 10, update index = 2 and search right side → low = 3
  • Binary search ends. The closest element is at index = 2 → arr2[2] = 10

Check the Condition:

  • |15 - 10| = 5
  • Since 5 > d, increment ans → ans = 1

Step 7: Final Result

  • Only 15 in arr1 satisfies the condition of being at a distance greater than d from all elements of arr2.
  • Therefore, ans = 1.

Step 8: Return the Answer

  • return ans → 1

Find the Distance Value Between Two Arrays Algorithm

Step 1. Initialize Variables

  • Get the sizes of arr1 and arr2.

Step 2. Sort arr2

  • Sorting helps in using binary search to efficiently find the closest value in arr2.
  • Use the sort function from the STL (Standard Template Library):

Step 3. Initialize Result Counter

  • Create a variable ans to store the count of valid elements in arr1.

Step 4. Start Outer Loop

  • Loop through each element in arr1.

Step 5. Initialize Binary Search Variables

  • Set the starting and ending indices for binary search.
  • Also, define an index variable to keep track of the closest value.

Step 6. Perform Binary Search

  • Start a while loop for binary search.
  • Find the middle index.
  • Case 1: If arr1[i] equals arr2[mid], the closest value is found. Break the loop:
  • Case 2: If arr1[i] is greater than arr2[mid]:
    • If the distance between arr1[i] and arr2[mid] is smaller than the current smallest distance, update the index.
    • Move to the right half.
  • Case 3: If arr1[i] is smaller than arr2[mid]:
    • If the distance between arr1[i] and arr2[mid] is smaller than the current smallest distance, update the index.
    • Move to the left half.

Step 7. Check Distance Condition

  • After the binary search, check if the minimum distance is greater than d. If yes increase ans by 1.

Step 8. Return Result

  • Finally, return the total valid count:

Find the Distance Value Between Two Arrays Leetcode Solution
Find the Distance Value Between Two Arrays Solution in C++ 
class Solution {
public:
    // Function to find the distance value
    int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {
		// Size of arr1
        int n = arr1.size();
		// Size of arr2 
        int m = arr2.size(); 

        // Step 1: Sort arr2 to allow efficient binary search
        sort(arr2.begin(), arr2.end());

        int ans = 0; // Counter for distance value elements

        // Step 2: Iterate over each element in arr1
        for(int i = 0; i < n; ++i) {
			// Binary search range
            int low = 0, high = m - 1; 
			// To store index of the closest value
            int index = 0; 

            // Step 3: Perform binary search to find closest value in arr2 to arr1[i]
            while (low <= high) {
                int mid = (low + high) / 2;

                // If exact match found, update index and exit search
                if (arr1[i] == arr2[mid]) {
                    index = mid;
                    break;
                }
                // If arr1[i] is greater, check right side
                else if (arr1[i] > arr2[mid]) {
                    // Update index if current difference is smaller than previous difference
                    if (abs(arr1[i] - arr2[mid]) < abs(arr1[i] - arr2[index])) {
                        index = mid;
                    }
                    low = mid + 1;
                }
                // If arr1[i] is smaller, check left side
                else {
                    // Update index if current difference is smaller than previous difference
                    if (abs(arr1[i] - arr2[mid]) < abs(arr1[i] - arr2[index])) {
                        index = mid;
                    }
                    high = mid - 1;
                }
            }

            // Step 4: Check if absolute difference exceeds threshold d
            if (abs(arr1[i] - arr2[index]) > d) {
				// Increment answer if condition satisfied
                ans++; 
            }
        }

        return ans;
    }
};

Find the Distance Value Between Two Arrays Solution in Java 
class Solution {
    // Function to find the distance value between two arrays
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
		// Length of arr1
        int n = arr1.length; 
		// Length of arr2
        int m = arr2.length; 
        
        // Step 1: Sort arr2 for binary search
        Arrays.sort(arr2);

        int ans = 0; // Counter for valid distance values

        // Step 2: Iterate through each element in arr1
        for (int i = 0; i < n; ++i) {
            int low = 0, high = m - 1;
			// To store the closest element in arr2
            int index = 0; 

            // Step 3: Binary search to find the closest element in arr2
            while (low <= high) {
                int mid = (low + high) / 2;

                if (arr1[i] == arr2[mid]) {
                    // If exact match found, update index and break
                    index = mid;
                    break;
                } else if (arr1[i] > arr2[mid]) {
                    // If arr1[i] > arr2[mid], search in the right half
                    if (Math.abs(arr1[i] - arr2[mid]) < Math.abs(arr1[i] - arr2[index])) {
                        index = mid;
                    }
                    low = mid + 1;
                } else {
                    // If arr1[i] < arr2[mid], search in the left half
                    if (Math.abs(arr1[i] - arr2[mid]) < Math.abs(arr1[i] - arr2[index])) {
                        index = mid;
                    }
                    high = mid - 1;
                }
            }

            // Step 4: Check the difference condition
            if (Math.abs(arr1[i] - arr2[index]) > d) {
                ans++;
            }
        }

        // Step 5: Return the result
        return ans;
    }
}

Find the Distance Value Between Two Arrays Solution in Python 
class Solution:
    # Function to find the distance value between two arrays
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        # Step 1: Sort arr2 to allow binary search for faster lookup
        arr2.sort()
        
        # Initialize counter for valid distance values
        ans = 0  

        # Step 2: Iterate over each element in arr1
        for num in arr1:
            # Initialize binary search range
            low, high = 0, len(arr2) - 1  
            # To keep track of the closest element in arr2
            index = 0  

            # Step 3: Perform binary search to find the closest element in arr2
            while low <= high:
                mid = (low + high) // 2  # Find the middle index

                if num == arr2[mid]:
                    # If the element in arr2 matches num exactly, update index and stop
                    index = mid
                    break
                elif num > arr2[mid]:
                    # If num is greater than arr2[mid]:
                    # - Check if this is the closest element found so far
                    if abs(num - arr2[mid]) < abs(num - arr2[index]):
                        # Update the closest index
                        index = mid  
                    # Move to the right half
                    low = mid + 1  
                else:
                    # If num is less than arr2[mid]:
                    # - Check if this is the closest element found so far
                    if abs(num - arr2[mid]) < abs(num - arr2[index]):
                        # Update the closest index
                        index = mid  
                    # Move to the left half
                    high = mid - 1  

            # Step 4: Check the distance condition:
            # If the absolute difference between num and the closest value in arr2 is greater than d
            if abs(num - arr2[index]) > d:
                ans += 1  # Increment counter

        # Step 5: Return the final count of valid distance values
        return ans

Find the Distance Value Between Two Arrays Solution in Javascript 
/**
 * @param {number[]} arr1 - First input array
 * @param {number[]} arr2 - Second input array
 * @param {number} d - Distance value threshold
 * @return {number} - Number of valid distance values
 */
var findTheDistanceValue = function(arr1, arr2, d) {
    // Step 1: Sort arr2 to enable efficient binary search
    arr2.sort((a, b) => a - b);

    let ans = 0; // Counter for valid distance values

    // Step 2: Iterate over each element in arr1
    for (let num of arr1) {
        let low = 0, high = arr2.length - 1; // Binary search range
        let index = 0; // To store the closest element in arr2

        // Step 3: Binary search to find the closest element in arr2
        while (low <= high) {
            let mid = Math.floor((low + high) / 2); // Find middle index

            if (num === arr2[mid]) {
                // If exact match is found, set index and break out
                index = mid;
                break;
            } else if (num > arr2[mid]) {
                // If num is greater than arr2[mid]:
                // - Check if it's closer than previously found value
                if (Math.abs(num - arr2[mid]) < Math.abs(num - arr2[index])) {
                    // Update the closest index
                    index = mid; 
                }

                // Move to the right half
                low = mid + 1; 
            } else {
                // If num is less than arr2[mid]:
                // - Check if it's closer than previously found value
                if (Math.abs(num - arr2[mid]) < Math.abs(num - arr2[index])) {
                    // Update the closest index
                    index = mid; 
                }
                // Move to the left half
                high = mid - 1; 
            }
        }

        // Step 4: Check if the closest element is within the distance threshold
        if (Math.abs(num - arr2[index]) > d) {
            // Increment the count if the condition is met
            ans++; 
        }
    }

    // Step 5: Return the result
    return ans;
};

Find the Distance Value Between Two Arrays Complexity Analysis

Time Complexity: O((n+m)logm)

Let's carefully analyze the time complexity step-by-step:

Step 1. Sorting Step

  • We sort arr2 before starting the main logic:
  • Sorting takes O(m×log m) time, where m is the size of arr2.

Step 2. Outer Loop Step

  • The outer loop runs over each element of arr1.
  • This loop runs n times, where n is the size of arr1.

Step 3. Binary Search Step

  • Inside the outer loop, we perform a binary search on arr2.
  • The binary search works by reducing the search space by half at each step.
  • Let's see how it happens:
    • Start with a search range of size m .
    • After the first comparison, the search space becomes m/2.
    • After the second comparison, the search space becomes m/4.
    • After the third comparison, the search space becomes m/8.
    • This continues until the search space reduces to 1.

General Pattern:

  • At each step, the search space is divided by 2.
  • Therefore, the number of steps required to reduce the search space to size 1 is approximately: log⁡2 m
  • Thus, the number of iterations in the while loop is log2 m.

Work Done Per Iteration:

  • Inside the loop, the following operations happen:
    • Computing mid = (low + high) / 2 → O(1)
    • Comparison and updating index, low, and high → O(1)
    • Total Work Per Iteration: O(1)

Number of Iterations: O(log⁡n)

Therefore, the total work done inside the loop is: O(1) ×O(log⁡n)=O(log⁡n)

Step 4. Distance Calculation and Condition Check Step

  • After binary search, the condition check takes O(1) time.

Step 5. Final Time Complexity

The overall time complexity is the sum of the following:

  1. Sorting step → O(m * log m)
  2. Outer loop → O(n)
  3. Binary search inside loop → O(log m)

O(mlog⁡m)+O(nlogm) = O((n+m)logm)

Space Complexity: O(n+m)

1. Auxiliary Space Complexity

Auxiliary space refers to the extra space used during the execution of the code (excluding the input).

  • Sorting arr2
    • The sort() function in C++ uses O(m) extra space internally for sorting (because C++’s std::sort() is implemented using a hybrid of quicksort, heapsort, and insertion sort).
    • Therefore, sorting contributes O(m) auxiliary space.
  • Binary Search Variables
    • Variables like low, high, mid, and index are simple integer variables, so they take O(1) extra space.
    • Therefore, binary search contributes O(1) auxiliary space.
  • Answer Counter
    • The variable ans used to store the final count takes O(1) space.

Total Auxiliary Space = O(m) + O(1) + O(1) = O(m)

2. Total Space Complexity

Total space complexity includes:

  • Input size – arr1 and arr2 are part of the input and not counted towards auxiliary space.
  • Therefore, total space complexity = size of input + auxiliary space = O(n + m) + O(m) = O(n+m)

where:

  • n = size of arr1
  • m = size of arr2

Total Overall Space = O(n + m)

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems: -

1. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

2. Find K Closest Elements

Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.

An integer a is closer to x than an integer b if:

  • |a - x| < |b - x|, or
  • |a - x| == |b - x| and a < b