Minimum Absolute Difference Between Elements With Constraint

Medium
1394.

Minimum Absolute Difference Between Elements With Constraint

Minimum Absolute Difference Between Elements With Constraint is a medium coding problem on arrays, binary search and ordered set, asked in Amazon, Google and Capital One interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} x
 * @return {number}
 */
var minAbsoluteDifference = function(nums, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Absolute Difference Between Elements With Constraint Solution

Minimum Absolute Difference Between Elements With Constraint solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Absolute Difference Between Elements With Constraint is a medium coding problem on arrays, binary search and ordered set, asked in Amazon, Google and Capital One interviews.

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

Hints for Minimum Absolute Difference Between Elements With Constraint

  1. Hint 1

    Fix the right index j. Its valid partners on the left are exactly nums[0..j-x] — a prefix that grows by one element as j moves right.

  2. Hint 2

    Among the values in that prefix, only the closest one below nums[j] and the closest one above it can give the minimum.

  3. Hint 3

    Keep the prefix in a sorted structure (an ordered set, or a Fenwick tree over compressed values) and look up the predecessor and successor of nums[j].

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

Java

public static int minAbsoluteDifference(int[] nums, int x) {
    TreeSet<Integer> seen = new TreeSet<>();
    int best = Integer.MAX_VALUE;
    for (int j = x; j < nums.length && best > 0; j++) {
        seen.add(nums[j - x]);
        int v = nums[j];
        Integer below = seen.floor(v), above = seen.ceiling(v);
        if (below != null) best = Math.min(best, v - below);
        if (above != null) best = Math.min(best, above - v);
    }
    return best;
}

C++

int minAbsoluteDifference(vector<int>& nums, int x) {
    set<int> seen;
    int best = INT_MAX;
    for (int j = x; j < (int)nums.size() && best > 0; j++) {
        seen.insert(nums[j - x]);
        int v = nums[j];
        auto it = seen.lower_bound(v);
        if (it != seen.end()) best = min(best, *it - v);
        if (it != seen.begin()) best = min(best, v - *prev(it));
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search