0967MediumArrayBinary SearchOrdered Set

Closest Pair at Least x Apart

Tracked in this browser only

Trains the technique from

LeetCode 2817Minimum Absolute Difference Between Elements With Constraint

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Readings are given as nums, along with a gap x.

Consider the pairs of positions i and j that sit at least x apart, that is where the difference of the positions is at least x. Return the smallest difference in value between the readings of any such pair, taken without sign.

A gap of 0 allows a position to be paired with itself, which gives a difference of nothing.

Examples

Example 1

Input: nums = [14, 3, 27, 9, 41, 6], x = 3
Output: 3

Positions three or more apart include 0 with 3, whose readings are 14 and 9, five apart, and 2 with 5, whose readings are 27 and 6. The closest such pair is the first.

Example 2

Input: nums = [5, 9], x = 0
Output: 0

With a gap of nothing a position pairs with itself, so the answer is nothing.

Example 3

Input: nums = [1, 2, 3, 4], x = 3
Output: 3

Only the two ends are three apart, and their readings differ by three.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= x <= nums.length - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_absolute_difference(nums: list[int], x: int) -> int:

Java

public int minAbsoluteDifference(int[] nums, int x)

The intended approach

Time O(n log n) for n readings: one search and one insertion each.Space O(n) for the sorted collection.

Walk the right end of the pair forward, keeping in a sorted collection every reading whose position is at least `x` behind it. As the right end moves on by one, exactly one more reading becomes eligible, so the collection only ever grows and each reading is added once. For the reading at the right end, the closest eligible partner is whichever of its neighbours in the sorted collection is nearer, which a search over the collection finds without looking at anything else. Taking the smallest such distance over all right ends gives the answer. A gap of nothing means the reading itself is eligible, which the same walk handles by adding it before searching.

Pythonentry point: min_absolute_difference

def min_absolute_difference(nums, x):
    import bisect
    n = len(nums)
    seen = []
    best = None
    for right in range(n):
        at = right - x
        if at >= 0:
            bisect.insort(seen, nums[at])
        if not seen:
            continue
        v = nums[right]
        pos = bisect.bisect_left(seen, v)
        if pos < len(seen):
            gap = seen[pos] - v
            if best is None or gap < best:
                best = gap
        if pos > 0:
            gap = v - seen[pos - 1]
            if best is None or gap < best:
                best = gap
    return best

The obvious version

Try every pair of positions at least the wanted gap apart and keep the smallest difference in value. Quadratic in the reading count and it keeps nothing between pairs.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_absolute_difference(nums, x):
    n = len(nums)
    best = None
    for i in range(n):
        for j in range(n):
            step = i - j
            if step < 0:
                step = -step
            if step < x:
                continue
            gap = nums[i] - nums[j]
            if gap < 0:
                gap = -gap
            if best is None or gap < best:
                best = gap
    return best

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in