Minimum Absolute Difference

Easy Arrays & Hashing Greedy Original on LeetCode

Minimum Absolute Difference is a easy arrays & hashing problem solved with the greedy pattern. The best approach, optimal (sort, then compare neighbours), runs in O(n log n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every pair) up.

Problem

You are given an array arr of distinct integers. Find the smallest absolute difference between any two of its elements, and return every pair of elements whose difference equals that minimum.

Write each pair as [a, b] with a < b, and list the pairs in ascending order of a.

Examples

Example 1

Input
arr = [9, 2, 5, 7]
Output
[[5, 7], [7, 9]]
Why
The closest any two values get is 2, and exactly two pairs reach it: 5 and 7, then 7 and 9.

Example 2

Input
arr = [-4, 10, 0]
Output
[[-4, 0]]
Why
Differences are 14, 4 and 10, so only the pair (-4, 0) has the smallest gap of 4.

Example 3

Input
arr = [6, 3, 4, 5]
Output
[[3, 4], [4, 5], [5, 6]]
Why
The values form a run of consecutive integers, so every adjacent pair is 1 apart.

Constraints

  • 2 <= arr.length <= 10^5
  • -10^6 <= arr[i] <= 10^6
  • All values in arr are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every pair)O(n²)O(n)
Optimal (sort, then compare neighbours)O(n log n)O(n)

1Brute force (check every pair)

TimeO(n²)There are n(n - 1)/2 pairs to compare.
SpaceO(n)The result list holds at most n - 1 pairs (all minimum pairs are neighbours in sorted order).

Compare every pair of values, track the smallest difference seen, and keep the list of pairs that achieve it. Sort the collected pairs at the end so they come out in ascending order.

  1. best = infinity, pairs = [].
  2. For every i < j, let a = min(arr[i], arr[j]), b = max(...), d = b - a.
  3. If d < best, reset pairs to [[a, b]] and best = d; if d == best, append [a, b].
  4. Sort pairs by their first value and return them.
class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int n = arr.length;
        long best = Long.MAX_VALUE;
        List<List<Integer>> pairs = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int a = Math.min(arr[i], arr[j]), b = Math.max(arr[i], arr[j]);
                long d = (long) b - a;
                if (d < best) {
                    best = d;
                    pairs.clear();
                    pairs.add(Arrays.asList(a, b));
                } else if (d == best) {
                    pairs.add(Arrays.asList(a, b));
                }
            }
        pairs.sort((x, y) -> Integer.compare(x.get(0), y.get(0)));
        return pairs;
    }
}

2Optimal (sort, then compare neighbours)

TimeO(n log n)Sorting dominates; the two scans are linear.
SpaceO(n)The output list (plus the sort's own stack).

Once the values are sorted, any pair that is not adjacent has at least one value between them, so its gap is at least as large as one of the neighbour gaps. That means only the n - 1 neighbour gaps can be the minimum. Sort, find the smallest neighbour gap, then collect every neighbour pair with that gap; they come out in ascending order for free.

  1. Sort arr.
  2. best = min over i of arr[i] - arr[i - 1].
  3. For each i from 1 to n - 1, if arr[i] - arr[i - 1] == best, append [arr[i - 1], arr[i]].
  4. Return the list.
class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int best = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) best = Math.min(best, arr[i] - arr[i - 1]);
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 1; i < arr.length; i++)
            if (arr[i] - arr[i - 1] == best) out.add(Arrays.asList(arr[i - 1], arr[i]));
        return out;
    }
}

Edge cases to test

  • Only two elements: the single pair is the answer
  • Negative and positive values mixed, gaps crossing zero
  • Every adjacent pair ties for the minimum (an arithmetic sequence)
  • Input not sorted, so the output order must come from sorting

Hints

Hint 1

Which two values can possibly be closest? Think about where they sit once the array is sorted.

Hint 2

After sorting, the minimum gap is always between neighbours, so only n - 1 differences matter.

Hint 3

Do two passes over the sorted array: one to find the smallest gap, one to collect every neighbour pair with that gap.

FAQ

What is the best time complexity for Minimum Absolute Difference?

Optimal (sort, then compare neighbours) runs in O(n log n) time and O(n) extra space. Sorting dominates; the two scans are linear.

Which pattern does Minimum Absolute Difference use?

It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.

Is there a brute force solution for Minimum Absolute Difference?

Yes. Brute force (check every pair) takes O(n²) time and O(n) space. Compare every pair of values, track the smallest difference seen, and keep the list of pairs that achieve it.

Which edge cases should I test for Minimum Absolute Difference?

Only two elements: the single pair is the answer; Negative and positive values mixed, gaps crossing zero; Every adjacent pair ties for the minimum (an arithmetic sequence); Input not sorted, so the output order must come from sorting.