Minimum Absolute Difference Queries

Medium
1377.

Minimum Absolute Difference Queries

Minimum Absolute Difference Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

The minimum absolute difference of an array is the smallest |a[i] - a[j]| over pairs of indices with a[i] != a[j]. If every element is the same, it is -1.

You are given nums (every value between 1 and 100) and queries, where queries[i] = [l, r] names the subarray nums[l..r] (inclusive). Return an array whose i-th entry is the minimum absolute difference of that subarray.

Example 1

Input
nums = [5,5,2,9,9], queries = [[0,1],[0,2],[2,4],[3,4]]
Output
[-1,3,7,-1]
Explanation
`[5,5]` and `[9,9]` hold one distinct value each; `[5,5,2]` gives 3; `[2,9,9]` gives 7.

Example 2

Input
nums = [4,1,7,3], queries = [[0,3],[1,2]]
Output
[1,6]
Explanation
The whole array sorted is 1, 3, 4, 7 — the closest pair is 3 and 4.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 100
  • 1 <= queries.length <= 2 * 10^4
  • 0 <= l < r < 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[][]} queries
 * @return {number[]}
 */
var minDifference = function(nums, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Absolute Difference Queries — Problem & Solution

Minimum Absolute Difference Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Absolute Difference Queries is a medium coding problem on arrays, hash table and binary search, asked in Amazon and Google interviews.

Problem statement

The minimum absolute difference of an array is the smallest |a[i] - a[j]| over pairs of indices with a[i] != a[j]. If every element is the same, it is -1.

You are given nums (every value between 1 and 100) and queries, where queries[i] = [l, r] names the subarray nums[l..r] (inclusive). Return an array whose i-th entry is the minimum absolute difference of that subarray.

Example 1

Input: nums = [5,5,2,9,9], queries = [[0,1],[0,2],[2,4],[3,4]]
Output: [-1,3,7,-1]
Explanation: `[5,5]` and `[9,9]` hold one distinct value each; `[5,5,2]` gives 3; `[2,9,9]` gives 7.

Example 2

Input: nums = [4,1,7,3], queries = [[0,3],[1,2]]
Output: [1,6]
Explanation: The whole array sorted is 1, 3, 4, 7 — the closest pair is 3 and 4.

Constraints

  • 2 <= nums.length <= 10^5
  • 1 <= nums[i] <= 100
  • 1 <= queries.length <= 2 * 10^4
  • 0 <= l < r < nums.length

Hints for Minimum Absolute Difference Queries

  1. Hint 1

    Values live in 1..100, so a query only needs to know which of the 100 values occur in its range.

  2. Hint 2

    Once you know the present values in increasing order, the answer is the smallest gap between consecutive present values.

  3. Hint 3

    Keep, for each value, the sorted list of indices where it appears; a binary search tells whether any of them lies in [l, r].

How to solve Minimum Absolute Difference Queries

With only 100 possible values, answer a query by walking the values in increasing order and asking, for each, whether it occurs inside [l, r]. Each value's occurrence positions are sorted, so that question is a single lower-bound search.

Approach

  1. For every value v in 1..100, record the indices where nums[i] == v (already in increasing order).
  2. For a query [l, r], set prev = -1, best = ∞, and loop v from 1 to 100.
  3. Binary-search the first position of v that is >= l; v is present when such a position exists and is <= r.
  4. When v is present and prev != -1, update best with v - prev; then set prev = v.
  5. The query's answer is best, or -1 if it never changed (fewer than two distinct values).

Why it works

The minimum difference between distinct values in a multiset is always attained by two values that are adjacent in sorted order, so scanning the present values from small to large and taking consecutive gaps is exact. Presence of v in [l, r] is equivalent to its first position at or after l being at most r.

Complexity

  • Time — O(n + q · 100 · log n)
  • Space — O(n)

Pitfalls

  • Equal elements do not count — the difference must be between distinct values.
  • A per-index prefix count table (n × 100) also works but uses 100× the memory.
  • Queries are inclusive on both ends.

Reference solution

Python

from typing import List
import bisect

def minDifference(nums: List[int], queries: List[List[int]]) -> List[int]:
    pos = [[] for _ in range(101)]
    for i, v in enumerate(nums):
        pos[v].append(i)
    res = []
    for l, r in queries:
        prev = -1
        best = 1000
        for v in range(1, 101):
            p = pos[v]
            if not p:
                continue
            k = bisect.bisect_left(p, l)
            if k < len(p) and p[k] <= r:
                if prev != -1 and v - prev < best:
                    best = v - prev
                prev = v
        res.append(-1 if best == 1000 else best)
    return res

Java

public static int[] minDifference(int[] nums, int[][] queries) {
    List<List<Integer>> pos = new ArrayList<>();
    for (int v = 0; v <= 100; v++) pos.add(new ArrayList<>());
    for (int i = 0; i < nums.length; i++) pos.get(nums[i]).add(i);
    int[] res = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int l = queries[q][0], r = queries[q][1];
        int prev = -1, best = 1000;
        for (int v = 1; v <= 100; v++) {
            List<Integer> p = pos.get(v);
            if (p.isEmpty()) continue;
            int lo = 0, hi = p.size();
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (p.get(mid) < l) lo = mid + 1; else hi = mid;
            }
            if (lo < p.size() && p.get(lo) <= r) {
                if (prev != -1 && v - prev < best) best = v - prev;
                prev = v;
            }
        }
        res[q] = best == 1000 ? -1 : best;
    }
    return res;
}

C++

vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
    vector<vector<int>> pos(101);
    for (int i = 0; i < (int)nums.size(); i++) pos[nums[i]].push_back(i);
    vector<int> res;
    for (auto& qr : queries) {
        int l = qr[0], r = qr[1];
        int prev = -1, best = 1000;
        for (int v = 1; v <= 100; v++) {
            const vector<int>& p = pos[v];
            if (p.empty()) continue;
            auto it = lower_bound(p.begin(), p.end(), l);
            if (it != p.end() && *it <= r) {
                if (prev != -1 && v - prev < best) best = v - prev;
                prev = v;
            }
        }
        res.push_back(best == 1000 ? -1 : best);
    }
    return res;
}

JavaScript

var minDifference = function(nums, queries) {
    var pos = [];
    for (var v = 0; v <= 100; v++) pos.push([]);
    for (var i = 0; i < nums.length; i++) pos[nums[i]].push(i);
    var res = [];
    for (var q = 0; q < queries.length; q++) {
        var l = queries[q][0], r = queries[q][1];
        var prev = -1, best = 1000;
        for (var w = 1; w <= 100; w++) {
            var p = pos[w];
            if (p.length === 0) continue;
            var lo = 0, hi = p.length;
            while (lo < hi) {
                var mid = (lo + hi) >> 1;
                if (p[mid] < l) lo = mid + 1; else hi = mid;
            }
            if (lo < p.length && p[lo] <= r) {
                if (prev !== -1 && w - prev < best) best = w - prev;
                prev = w;
            }
        }
        res.push(best === 1000 ? -1 : best);
    }
    return res;
};

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 · Hashing: Hash Maps and Hash Sets