Minimum Absolute Difference: Sorting and Adjacent Pairs

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference. Return a list of pairs [a, b] where a is less than b, sorted in ascending order by a.

This is LeetCode 1200: Minimum Absolute Difference, and it is a clean introduction to the pattern of sorting first, then scanning adjacent elements. The technique shows up in many problems that ask about closest values, smallest gaps, or nearest neighbors in a collection.

Why this problem matters

Interview problems that ask about "minimum difference" or "closest pair" in an unsorted array are testing whether you recognize that sorting unlocks the answer. Without sorting, you would need to compare every pair, which takes O(n^2) time. With sorting, the minimum difference is guaranteed to appear between two neighbors, and you only need a single pass.

This pattern extends to problems like finding the two closest points on a number line, merging intervals, or detecting near-duplicates. Whenever a problem involves pairwise comparisons on values, sorting first almost always reduces the work.

The key insight

In a sorted array, the minimum absolute difference can only occur between adjacent elements. Why? If you pick two elements that are not adjacent, there is at least one element between them. That in-between element is closer to one of the two you picked, so its difference with that neighbor is smaller. This means you never need to look beyond adjacent pairs.

This reduces the problem to three steps: sort the array, scan adjacent pairs to find the minimum difference, then collect all pairs that match it.

The solution

def minimum_abs_difference(arr: list[int]) -> list[list[int]]:
    arr.sort()
    min_diff = float('inf')

    for i in range(1, len(arr)):
        min_diff = min(min_diff, arr[i] - arr[i - 1])

    result = []
    for i in range(1, len(arr)):
        if arr[i] - arr[i - 1] == min_diff:
            result.append([arr[i - 1], arr[i]])

    return result

Let's walk through what each piece does.

The first line sorts the array in place. This is the move that makes everything else possible. Once the values are in order, the minimum absolute difference must live between two neighbors.

The first loop finds the minimum difference. It walks through every adjacent pair and tracks the smallest gap seen so far. Because the array is sorted, arr[i] - arr[i - 1] is always non-negative, so we do not need abs().

The second loop collects the answer. It walks through the pairs again and appends every pair whose difference equals the minimum. The pairs are automatically in ascending order by a because the array is sorted.

Visual walkthrough

Let's trace through arr = [4, 2, 1, 3] step by step. Watch how sorting transforms a scattered collection into an ordered sequence where the answer becomes obvious.

Every adjacent pair has a difference of 1, so all three pairs end up in the result. In cases where only some pairs match the minimum, the second pass filters out the rest.

Complexity analysis

Time is O(n log n), dominated by the sort. The two linear scans add O(n) each, but that does not change the overall bound. Sorting is the bottleneck.

Space is O(n) for the result list. In the worst case, every adjacent pair shares the same difference (like [1, 2, 3, 4]), so the result holds n - 1 pairs. The sort itself uses O(log n) auxiliary space in most implementations, which is smaller than the result.

The building blocks

1. Sort then scan adjacent pairs

arr.sort()
for i in range(1, len(arr)):
    diff = arr[i] - arr[i - 1]

This is the core pattern. Any time a problem asks about the minimum (or maximum) difference between elements, sorting and scanning neighbors is the go-to approach. You will see this in problems like "Contains Duplicate III" (LeetCode 220), "Minimum Distance Between BST Nodes" (LeetCode 783), and any problem where you need the closest pair of values.

2. Two-pass collect with a threshold

min_val = float('inf')
for x in data:
    min_val = min(min_val, compute(x))

results = [x for x in data if compute(x) == min_val]

The first pass finds the threshold, and the second pass collects everything that meets it. This pattern appears whenever a problem says "find all elements that share some optimal property." It separates the concern of finding the optimum from the concern of gathering the results, which keeps the logic clean and easy to verify.

Edge cases

• Array of size 2: only one pair exists, and it is automatically the answer.
• All elements equally spaced (like [1, 3, 5, 7]): every adjacent pair has the same difference, so all pairs appear in the result.
• Large negative and positive values: sorting handles negatives correctly, and arr[i] - arr[i - 1] on a sorted array is always non-negative, so no abs() is needed.
• Already sorted input: the sort is a no-op, and the scan proceeds normally. No special handling required.
• Minimum difference of 0 is impossible: the problem states all integers are distinct, so adjacent differences are always at least 1.

From understanding to recall

You now know the full approach: sort, scan for the minimum gap, collect matching pairs. The logic is short and the idea is intuitive. But under interview pressure, small details trip people up. Do you scan from index 0 or 1? Do you need abs()? Do you collect pairs as [arr[i-1], arr[i]] or [arr[i], arr[i-1]]?

These are not conceptual gaps. They are recall gaps. Spaced repetition closes them. You practice writing the sort-and-scan loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "minimum difference" in a problem statement, and the template flows out without hesitation.

Related posts

• Sort an Array - The foundational sorting problem that teaches you to implement sorting from scratch
• Contains Duplicate - Another problem where sorting (or hashing) transforms an O(n^2) brute force into an efficient scan
• Merge Sorted Array - Practice working with sorted data and the two-pointer pattern that builds on sorting intuition

CodeBricks breaks Minimum Absolute Difference into its sort-then-scan and two-pass-collect building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sorting problem shows up in your interview, you do not think about it. You just write it.