Get started

Minimum Absolute Difference Between Elements With Constraint — Medium Problem & Solution

Given an array nums and an integer x, consider every pair of indices i and j that are at least x apart, i.e. |i - j| >= x.

Problem statement

Given an array nums and an integer x, consider every pair of indices i and j that are at least x apart, i.e. |i - j| >= x.

Return the smallest value of |nums[i] - nums[j]| over all such pairs. (When x is 0 an index may be paired with itself, so the answer is 0.)

Example 1

Input: nums = [9,2,6,11], x = 2
Output: 2
Explanation: Indices 0 and 3 hold 9 and 11, three apart; indices 0 and 2 give 3.

Example 2

Input: nums = [5,3,2,10,15], x = 1
Output: 1
Explanation: Neighbours 3 and 2 differ by 1.

Example 3

Input: nums = [1,2,3,4], x = 3
Output: 3
Explanation: Only indices 0 and 3 are far enough apart.

Constraints

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

How to solve Minimum Absolute Difference Between Elements With Constraint

Sweep j from x to n - 1, adding nums[j - x] to a sorted collection just before handling j. The collection then holds exactly the elements far enough to the left, and the best partner for nums[j] is its predecessor or successor there.

Approach

  1. For j = x, x + 1, …, n - 1: insert nums[j - x] into a sorted multiset.
  2. Find the largest stored value <= nums[j] and the smallest stored value >= nums[j] (binary search / ordered-set floor and ceiling).
  3. Update the answer with the distances to both; stop early if it reaches 0.
  4. Without a built-in ordered set, compress the values and use a Fenwick tree: count the stored values <= nums[j], then find the c-th and (c + 1)-th smallest with a Fenwick descent.

Why it works

Every valid pair has a right end j and a left end i <= j - x, so considering each j against the whole prefix 0..j-x covers all pairs (pairs are unordered, so the mirrored case adds nothing). For a fixed nums[j], the closest value in a set is always its floor or its ceiling.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Insert nums[j - x] before querying nums[j] — with x = 0 that pairs an index with itself and correctly yields 0.
  • A plain sorted array with insertions is O(n²) in the worst case; use a balanced tree or a Fenwick tree for 10^5 elements.
  • Look at both neighbours, not just the floor.

Reference solution

Python

from typing import List
import bisect

def minAbsoluteDifference(nums: List[int], x: int) -> int:
    seen = []
    best = 1 << 31
    for j in range(x, len(nums)):
        bisect.insort(seen, nums[j - x])
        v = nums[j]
        k = bisect.bisect_left(seen, v)
        if k < len(seen):
            best = min(best, seen[k] - v)
        if k > 0:
            best = min(best, v - seen[k - 1])
        if best == 0:
            break
    return best

JavaScript

var minAbsoluteDifference = function(nums, x) {
    var n = nums.length;
    var sorted = nums.slice().sort(function(a, b) { return a - b; });
    var vals = [];
    for (var i = 0; i < n; i++) if (i === 0 || sorted[i] !== sorted[i - 1]) vals.push(sorted[i]);
    var m = vals.length;
    var tree = new Array(m + 1).fill(0);
    var step = 1;
    while (step * 2 <= m) step *= 2;
    var rankOf = function(v) {
        var lo = 0, hi = m;
        while (lo < hi) {
            var mid = (lo + hi) >> 1;
            if (vals[mid] < v) lo = mid + 1; else hi = mid;
        }
        return lo + 1;
    };
    var kth = function(k) {
        var pos = 0;
        for (var s = step; s > 0; s >>= 1) {
            if (pos + s <= m && tree[pos + s] < k) { pos += s; k -= tree[pos]; }
        }
        return pos + 1;
    };
    var best = 2147483647, inserted = 0;
    for (var j = x; j < n && best > 0; j++) {
        for (var p = rankOf(nums[j - x]); p <= m; p += p & -p) tree[p]++;
        inserted++;
        var v = nums[j], c = 0;
        for (var q = rankOf(v); q > 0; q -= q & -q) c += tree[q];
        if (c > 0) {
            var below = vals[kth(c) - 1];
            if (v - below < best) best = v - below;
        }
        if (c < inserted) {
            var above = vals[kth(c + 1) - 1];
            if (above - v < best) best = above - v;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 988 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search