LeetCode Problem 2817

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Ordered Set

Solution

LeetCode 2817 - Minimum Absolute Difference Between Elements With Constraint

Problem Understanding

We are given an integer array nums and an integer x. We need to find two elements whose indices are separated by at least x, and among all such valid pairs, return the minimum possible absolute difference between their values.

More formally, we must find:

$$\min \left( |nums[i] - nums[j]| \right)$$

subject to:

$$|i - j| \ge x$$

The input consists of:

• nums, an array of length up to 10^5
• x, the minimum required distance between indices

The output is a single integer representing the smallest absolute value difference among all valid pairs.

The constraints are important:

• nums.length can be as large as 100,000
• Each value can be as large as 10^9

Since the array can contain one hundred thousand elements, any algorithm that examines all pairs will be far too slow. We need something close to O(n log n).

Several observations help clarify the problem:

When processing position i, any index j is valid if |i - j| >= x. Instead of checking all such indices repeatedly, we need a way to efficiently maintain the set of values that are far enough away from the current position.

An important edge case is x = 0. In that case every pair of indices is valid, including pairing an element with itself conceptually during processing. Since the absolute difference between a value and itself is zero, the answer must be 0.

Another important case occurs when only a few pairs satisfy the distance constraint, such as x = n - 1. Then only elements near opposite ends of the array can participate.

The problem guarantees:

• The array contains at least one element.
• 0 <= x < nums.length.
• All values are positive integers.

Approaches

Brute Force

The most straightforward solution is to examine every possible pair of indices.

For every index i, we iterate through every index j. Whenever |i - j| >= x, we compute:

$$|nums[i] - nums[j]|$$

and update the minimum answer.

This approach is correct because it explicitly checks every valid pair and therefore cannot miss the optimal one.

However, there are O(n²) pairs. With n = 100000, this would require roughly ten billion comparisons, which is completely impractical.

Key Insight

The absolute difference between two numbers is minimized when the numbers are close in value.

Suppose we are currently processing index i.

Any index j <= i - x automatically satisfies:

$$i - j \ge x$$

Therefore, when examining nums[i], we only need access to all values that appear at least x positions before it.

If we maintain those values in a sorted data structure, then for nums[i] the closest value in magnitude must be either:

• The first value greater than or equal to nums[i]
• The largest value strictly less than nums[i]

No other value can produce a smaller absolute difference.

Thus, for every position:

1. Insert nums[i - x] into a sorted structure.
2. Find the insertion position of nums[i].
3. Check neighboring values.
4. Update the minimum difference.

A balanced binary search tree or ordered set supports insertion and predecessor/successor queries in O(log n) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every valid pair
Optimal	O(n log n)	O(n)	Maintains eligible values in sorted order

Algorithm Walkthrough

1. Handle the special case x == 0.

Every index is valid with itself because the distance requirement is zero. The minimum possible absolute difference is therefore 0. 2. Create an empty sorted container.

This container will store all values whose indices are at least x positions behind the current index. 3. Initialize the answer to positive infinity.

As we discover candidate pairs, we will continuously minimize this value. 4. Iterate through the array from left to right using index i.

Before processing nums[i], insert nums[i - x] into the sorted container whenever i >= x. 5. Find the insertion position of nums[i].

Using binary search, determine where nums[i] would appear in sorted order. 6. Check the successor.

If a value exists at the insertion position, compute the difference between that value and nums[i]. 7. Check the predecessor.

If a value exists immediately before the insertion position, compute the difference between that value and nums[i]. 8. Update the answer.

Since the closest value in sorted order must be one of these two neighbors, the minimum difference for the current element is found among them. 9. Continue until all elements have been processed. 10. Return the smallest difference found.

Why it works

At iteration i, the sorted structure contains exactly the values whose indices satisfy j <= i - x. Every value in the structure therefore forms a valid pair with nums[i].

Among all values in a sorted set, the minimum absolute difference to a target value must come from either its predecessor or successor. Any other value is farther away numerically and therefore cannot yield a smaller difference.

Since every valid pair is considered when its later index is processed, and the closest candidates are always checked, the algorithm finds the global minimum absolute difference.

Python Solution

from typing import List
from bisect import bisect_left, insort

class Solution:
    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        if x == 0:
            return 0

        sorted_values = []
        answer = float("inf")

        for i in range(x, len(nums)):
            insort(sorted_values, nums[i - x])

            pos = bisect_left(sorted_values, nums[i])

            if pos < len(sorted_values):
                answer = min(
                    answer,
                    abs(sorted_values[pos] - nums[i])
                )

            if pos > 0:
                answer = min(
                    answer,
                    abs(sorted_values[pos - 1] - nums[i])
                )

        return answer

The implementation follows the algorithm directly.

The special case x == 0 is handled immediately because the answer must be zero.

sorted_values stores all values that are far enough behind the current index to satisfy the distance constraint. When processing index i, we first insert nums[i - x], ensuring that every value in the structure corresponds to a valid earlier index.

bisect_left finds where the current value would be inserted in sorted order. The value at that position is the successor, while the value immediately before it is the predecessor.

Checking only these two neighbors is sufficient because they are the closest values numerically. Each candidate difference is used to update the global minimum.

After all indices are processed, the smallest recorded difference is returned.

Go Solution

package main

import (
	"math"
	"sort"
)

func minAbsoluteDifference(nums []int, x int) int {
	if x == 0 {
		return 0
	}

	sortedValues := make([]int, 0)
	ans := math.MaxInt

	for i := x; i < len(nums); i++ {
		val := nums[i-x]

		insertPos := sort.SearchInts(sortedValues, val)
		sortedValues = append(sortedValues, 0)
		copy(sortedValues[insertPos+1:], sortedValues[insertPos:])
		sortedValues[insertPos] = val

		pos := sort.SearchInts(sortedValues, nums[i])

		if pos < len(sortedValues) {
			diff := sortedValues[pos] - nums[i]
			if diff < 0 {
				diff = -diff
			}
			if diff < ans {
				ans = diff
			}
		}

		if pos > 0 {
			diff := sortedValues[pos-1] - nums[i]
			if diff < 0 {
				diff = -diff
			}
			if diff < ans {
				ans = diff
			}
		}
	}

	return ans
}

The Go version uses sort.SearchInts to perform binary searches.

Unlike Python, Go does not provide a built in ordered multiset. The code therefore maintains a sorted slice manually. A binary search determines the insertion position, then copy shifts elements to create space.

The logic for finding predecessor and successor remains identical to the Python implementation.

It is worth noting that slice insertion in Go is linear time. In competitive programming environments, this solution is commonly accepted because the intended implementation assumes an ordered set. In production code, a balanced tree implementation would preserve the theoretical O(n log n) complexity.

Worked Examples

Example 1

Input:

nums = [4,3,2,4]
x = 2

i	Inserted Value	Sorted Set	Current Value	Candidates	Best Answer
2	4	[4]	2	4 → diff 2	2
3	3	[3,4]	4	4 → diff 0	0

Result:

0

Example 2

Input:

nums = [5,3,2,10,15]
x = 1

i	Inserted Value	Sorted Set	Current Value	Candidates	Best Answer
1	5	[5]	3	5 → 2	2
2	3	[3,5]	2	3 → 1	1
3	2	[2,3,5]	10	5 → 5	1
4	10	[2,3,5,10]	15	10 → 5	1

Result:

1

Example 3

Input:

nums = [1,2,3,4]
x = 3

i	Inserted Value	Sorted Set	Current Value	Candidates	Best Answer
3	1	[1]	4	1 → 3	3

Result:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each insertion and neighbor lookup in an ordered set costs O(log n)
Space	O(n)	The ordered set may store up to n values

The algorithm processes each element exactly once. For every position, it performs one insertion and one binary search in the ordered structure. Since both operations take logarithmic time in a balanced search tree, the overall complexity is O(n log n). The auxiliary storage grows linearly with the number of inserted elements.

Test Cases

from typing import List

s = Solution()

assert s.minAbsoluteDifference([4, 3, 2, 4], 2) == 0  # provided example 1
assert s.minAbsoluteDifference([5, 3, 2, 10, 15], 1) == 1  # provided example 2
assert s.minAbsoluteDifference([1, 2, 3, 4], 3) == 3  # provided example 3

assert s.minAbsoluteDifference([7], 0) == 0  # single element
assert s.minAbsoluteDifference([1, 100], 1) == 99  # only valid pair
assert s.minAbsoluteDifference([5, 5, 5, 5], 1) == 0  # duplicate values
assert s.minAbsoluteDifference([5, 5, 5, 5], 3) == 0  # duplicates far apart
assert s.minAbsoluteDifference([1, 10, 20, 30], 2) == 19  # larger spacing
assert s.minAbsoluteDifference([8, 1, 6, 3, 8], 2) == 0  # equal values satisfy constraint
assert s.minAbsoluteDifference([1, 2, 1000000000], 1) == 1  # large values
assert s.minAbsoluteDifference([10, 9, 8, 7, 6], 1) == 1  # decreasing sequence
assert s.minAbsoluteDifference([1, 100, 2, 99, 3], 2) == 2  # alternating large and small
assert s.minAbsoluteDifference([4, 1, 7, 3, 9, 2], 5) == 2  # x close to n - 1
assert s.minAbsoluteDifference([100, 200, 300], 0) == 0  # x = 0 edge case

Test Summary

Test	Why
[4,3,2,4], x=2	Verifies duplicate values create answer 0
[5,3,2,10,15], x=1	Basic mixed values
[1,2,3,4], x=3	Only one valid pair
[7], x=0	Minimum size input
[1,100], x=1	Smallest nontrivial array
[5,5,5,5], x=1	Duplicate values
[5,5,5,5], x=3	Duplicates with large distance requirement
[1,10,20,30], x=2	Distance restriction changes answer
[8,1,6,3,8], x=2	Equal values far apart
[1,2,1000000000], x=1	Large numeric range
[10,9,8,7,6], x=1	Monotonic decreasing sequence
[1,100,2,99,3], x=2	Multiple competing candidates
[4,1,7,3,9,2], x=5	Constraint near maximum
[100,200,300], x=0	Special case where answer is always 0

Edge Cases

Case 1: x = 0

This is the most important special case. Every index automatically satisfies the distance requirement with itself because |i - i| = 0. The minimum possible absolute difference is therefore 0.

A solution that blindly performs ordered set processing might miss this observation. The implementation explicitly returns 0 immediately.

Case 2: x = n - 1

When the distance constraint is nearly the entire length of the array, very few pairs are valid. In many cases only one pair can be chosen.

For example:

nums = [1, 5, 9, 12]
x = 3

Only indices (0, 3) satisfy the requirement. The algorithm handles this naturally because values enter the ordered structure only when they become eligible.

Case 3: Duplicate Values Far Apart

Consider:

nums = [7, 1, 7]
x = 2

The optimal answer is 0.

A buggy implementation that only checks nearby indices or uses an incorrect sliding window could miss the matching values. Because the ordered structure always contains all valid earlier values, the algorithm detects the duplicate immediately and updates the answer to zero.

Case 4: Very Large Numbers

The values can be as large as 10^9.

For example:

nums = [1, 1000000000]
x = 1

The difference is 999999999, which still fits comfortably inside standard integer types used by both Python and Go. The implementation performs ordinary integer arithmetic without overflow concerns under the given constraints.