Abstract / Summary

Given two arrays, count how many elements in the first array have no pair in the second array within a given distance.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 72% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Sorting
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that computes the “distance value” between two integer arrays given a tolerance d. For each element in the first array, the algorithm determines whether there exists any element in the second array whose absolute difference does not exceed d. If no such element exists, the element contributes to the final count. The solution leverages sorting and binary search to achieve efficient look-ups.

Sorting the Second Array

The first decisive operation is to sort the second input array. Sorting places the elements in non-decreasing order, which is a prerequisite for applying binary search.

arr2.sort()

By arranging arr2 in order, the algorithm can later locate the insertion point for any value from arr1 in logarithmic time.

Iterating Over the First Array

The core loop processes each element of the first array sequentially. A running total, result, is initialized to zero and incremented only when the current element satisfies the distance condition.

result = 0
for a in arr1:
    ...

Each iteration isolates a single value a from arr1 for analysis.

Determining the Insertion Position

For the current element a, the algorithm computes the leftmost index in the sorted arr2 where a could be inserted while preserving order. This index, pos, is obtained via the standard library’s binary search routine.

pos = bisect_left(arr2, a)

The returned position indicates the first element in arr2 that is not less than a. This information is sufficient to examine at most two neighboring elements for the distance condition.

Checking the Candidate at the Insertion Point

If the insertion position lies within the bounds of arr2, the element at that index is a potential violator of the distance rule. The algorithm evaluates the absolute difference and, if it does not exceed d, skips counting the current a.

if pos < len(arr2) and abs(arr2[pos] - a) <= d:
    continue

The continue statement aborts the current iteration, moving to the next element of arr1.

Checking the Immediate Predecessor

When the insertion point is not at the very beginning of arr2, the element immediately before pos is also a candidate for violating the distance rule. The code performs a similar check on this predecessor.

if pos > 0 and abs(arr2[pos - 1] - a) <= d:
    continue

If this predecessor is within distance d, the iteration is likewise terminated early.

Accumulating the Result

If neither the element at pos nor its predecessor falls within the prohibited distance, the current element a is counted toward the final distance value.

result += 1

After all elements of arr1 have been examined, the method returns the accumulated count.

return result

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without additional code.

When arr2 is empty, the binary search returns 0, and both conditional checks evaluate to false because the length check fails and the predecessor check is bypassed. Consequently, every element of arr1 contributes to the result, which matches the definition of distance value when the second array contains no elements.

If an element of arr1 is smaller than all elements of arr2, the insertion position becomes 0. The first conditional check examines the element at index 0; the second check is skipped because pos > 0 is false. This ensures that only the smallest element of arr2 is considered, correctly handling the lower bound scenario.

Conversely, when an element of arr1 exceeds all elements of arr2, the insertion position equals the length of arr2. The first conditional check is bypassed because pos < len(arr2) is false, while the second check evaluates the last element of arr2 (index pos-1). This covers the upper bound case.

When duplicate values exist in arr2, the binary search returns the leftmost occurrence. The algorithm still inspects the element at that position and its immediate predecessor, guaranteeing that any duplicate that could violate the distance rule is examined.

The tolerance d may be zero, reducing the condition to exact equality. The same logic applies: the algorithm checks whether any element in arr2 equals the current a.

Performance Optimizations

Sorting arr2 once at the beginning transforms the problem from a naïve quadratic scan into a series of logarithmic look-ups. The use of bisect_left provides a binary search that runs in logarithmic time relative to the size of arr2.

By limiting the distance verification to at most two elements-the one at the insertion point and its immediate predecessor-the method avoids scanning the entire arr2 for each a. This selective checking is sufficient because any element farther away in the sorted order would have an absolute difference larger than the closest candidate already examined.

The early continue statements prevent unnecessary increments of the result counter and skip the remaining checks for a given a as soon as a violating element is found. This short-circuiting reduces the number of arithmetic operations performed during the loop.

Overall, the combination of a single sort, binary search for each element, and minimal neighbor checks yields an implementation that scales efficiently with the input sizes.

Imagine there are two boxes of number cards. The first box has some numbers, and the second box has others. There is also a special magic number called d. The goal is to look at each number in the first box one by one and see if it is far enough away from every single number in the second box.

First, the second box is sorted from the smallest number to the largest number so they are all in a neat line. For every number in the first box, the code tries to find the best spot where that number would fit into the line of the second box. Once that spot is found, the code checks the number right next to it in both directions. If the difference between the first box number and either of those neighboring numbers is smaller than or equal to the magic number, then the number is too close. If a number is not too close to either of those neighbors, it means it is far enough away from everything in the second box, so a point is added to the total score.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python				TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java	Go		Python			Rust	TS
	Progiez	C++		Java			Python
github	BigEggStudy							C#
	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim								C
	everthis		JS
	fartem					Ruby
	fsq	C++
	halfrost				Go
	JoshCrozier		JS
	keineahnung2345	C++
	lkwq007						Python
	lzl124631x	C++
	muhammadfarhankt				Go
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
lzl124631x	C++
muhammadfarhankt	Go
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality