easy

Minimum Absolute Difference

Find every pair of numbers with the smallest possible difference.

1. Define the problem

Minimum Absolute Difference

Given an array of distinct integers arr, find the minimum absolute difference between any two elements, and return every pair that achieves it, as [a, b] with a < b, sorted in ascending order. Mark every value present in a presence bucket sized to the range between the smallest and largest value, then scan the buckets in order — the minimum gap can only ever appear between neighboring occupied buckets.

Constraints

  • 2 ≤ arr.length ≤ 105
  • -106 ≤ arri ≤ 106
  • All the integers of arr are unique

Example

Inputarr = [4, 2, 1, 3]
Output[[1, 2], [2, 3], [3, 4]]

Explanation Sorted, arr is [1, 2, 3, 4]. Every consecutive gap is 1, which is the minimum, so every consecutive pair is returned.

2. Know the words first

In plain terms

Presence bucket
An array indexed by value that just records whether that value showed up, not how many times — used here since arr's values are distinct.
3. Visualize the solution

Bucket every value, then scan neighbors for the smallest gap

Bucket every value, then scan neighbors for the smallest gap
Statusinit

arr=[4, 2, 1, 3]. Find the min and max to size the presence buckets.

What happens in this step

arr = [4, 2, 1, 3]

lo = 1 (smallest), hi = 4 (largest)

Bucket array sized hi - lo + 1 = 4, indices 0..3 representing values 1..4.
Step 1 of 5

Steps to visualize

  1. Find the smallest and largest value to size the bucket range.
  2. Mark a bucket as present for every value in arr.
  3. Scan the buckets from smallest to largest, comparing each occupied bucket to the previous one.
  4. Keep only the pairs whose gap matches the smallest gap seen so far.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Bucket every value, then scan neighbors for the smallest gap
Statusinit

arr=[4, 2, 1, 3]. Find the min and max to size the presence buckets.

What happens in this step

arr = [4, 2, 1, 3]

lo = 1 (smallest), hi = 4 (largest)

Bucket array sized hi - lo + 1 = 4, indices 0..3 representing values 1..4.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function minimumAbsDifference(arr) {
  let lo = arr[0];
  let hi = arr[0];

  for (const num of arr) {
    if (num < lo) lo = num;
    if (num > hi) hi = num;
  }

  const present = new Array(hi - lo + 1).fill(false);

  for (const num of arr) {
    present[num - lo] = true;
  }

  let minDiff = Infinity;
  let prev = -1;
  let pairs = [];

  for (let i = 0; i < present.length; i++) {
    if (!present[i]) continue;

    if (prev !== -1) {
      const diff = i - prev;
      if (diff < minDiff) {
        minDiff = diff;
        pairs = [[prev + lo, i + lo]];
      } else if (diff === minDiff) {
        pairs.push([prev + lo, i + lo]);
      }
    }

    prev = i;
  }

  return pairs;
}
Time
O(n + k)
Space
O(k)
6. Test cases

Test cases

InputExpectedCovers
arr = [4, 2, 1, 3][[1, 2], [2, 3], [3, 4]]example from the docstring
arr = [1, 3, 6, 10, 15][[1, 3]]only one pair achieves the minimum gap
arr = [3, 8, -10, 23, 19, -4, -14, 27][[-14, -10], [19, 23], [23, 27]]negative values with several pairs tied for the minimum gap
arr = [5, 1][[1, 5]]smallest valid input, only one possible pair
arr = [-1, 1, 0][[-1, 0], [0, 1]]values spanning zero with two tied pairs
arr = [1, 100, 2, 50][[1, 2]]a wide range of values with one clearly smallest gap

Keep reading