Minimum Absolute Difference

The problem. Given an array of distinct integers arr, find the minimum absolute difference between any two elements, and return every pair [a, b] with that difference, with a < b, in ascending order of a.

Example

arr = [4, 2, 1, 3]                    ->  [[1,2], [2,3], [3,4]]
arr = [1, 3, 6, 10, 15]               ->  [[1,3]]
arr = [3, 8, -10, 23, 19, -4, -14, 27] ->  [[-14,-10], [19,23], [23,27]]

The idea: the closest pair is always adjacent once sorted

In sorted order, if a < b < c, then c − a is bigger than both b − a and c − b. So a pair that isn't adjacent can never be the closest — some value in between is closer to each of them. That leaves only the n − 1 gaps between neighbours: find the smallest, then collect every neighbouring pair with that gap. Because we walk in sorted order, the pairs come out already in the required order.

1. Brute force: every pair

1function minimumAbsDifference(arr) {2  let best = Infinity;3  for (let i = 0; i < arr.length; i++)4    for (let j = i + 1; j < arr.length; j++) best = Math.min(best, Math.abs(arr[i] - arr[j]));5  const pairs = [];6  for (let i = 0; i < arr.length; i++)7    for (let j = i + 1; j < arr.length; j++)8      if (Math.abs(arr[i] - arr[j]) === best) pairs.push([Math.min(arr[i], arr[j]), Math.max(arr[i], arr[j])]);9  return pairs.sort((p, q) => p[0] - q[0]);10}

Time O(n²), space O(n²) in the worst case for the pairs list. Every pair is compared, though only neighbours ever matter.

2. Sort, then look at neighbouring gaps

1function minimumAbsDifference(arr) {2  const a = [...arr].sort((x, y) => x - y);3  let best = Infinity;4  for (let i = 1; i < a.length; i++) best = Math.min(best, a[i] - a[i - 1]);   // the closest pair is always adjacent5  const pairs = [];6  for (let i = 1; i < a.length; i++) {7    if (a[i] - a[i - 1] === best) pairs.push([a[i - 1], a[i]]);8  }9  return pairs;10}

Time O(n log n), space O(n) for the sorted copy and the answer. Two linear passes after the sort.

Comparing the approaches

When values lie in a small range, a counting sort makes approach 2 linear: O(n + range).

Edge cases to test

Variations