Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Sort the array, then the pair(s) with the smallest absolute difference must be ADJACENT in sorted order. Make one pass to find the minimum adjacent gap, then a second pass to collect every adjacent pair achieving that gap, emitting each pair smaller-value-first. O(n log n) for the sort dominates.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realise that sorting makes the minimum-difference pair adjacent, eliminating the O(n²) all-pairs comparison, and whether you correctly handle ties by emitting every minimal pair.
Where candidates slip
Trying to find the answer in a single pass (you can't collect pairs before you know the minimum), or stopping at the first minimal pair instead of reporting all ties.
How to stand out
Prove the adjacency claim in one sentence (if a closest pair were non-adjacent, the element between them would be even closer to one of them), then do the clean two-pass collect.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewFind closest pair(s) by valueCompare every pair?Brute forceSort firstExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — All Pairs
1Hint 1Explore hintHide hint
The literal question is 'smallest difference over all pairs'. What is the most direct way to enumerate every pair?
2Hint 2Explore hintHide hint
Two nested loops over i < j; track the minimum |arr[i] - arr[j]| seen so far.
3Hint 3Explore hintHide hint
Because ties must all be reported, a single 'best' variable is not enough — you'd need a second pass or a list you prune whenever a smaller difference appears.
A · Core idea
Enumerate every unordered pair (i, j) with i < j, compute |arr[i] − arr[j]|, and keep the minimum. To also report ties you maintain a list: when you find a strictly smaller difference you clear the list and start it fresh; when you find an equal difference you append.
Why it is the honest starting point. It maps the words of the problem straight onto code with zero insight required, which is exactly why it's worth stating before optimising — it frames the O(n²) cost the better solution removes.
Why it fails the constraints. With n up to 2·10⁵, the quadratic pair count is ~`2·10¹⁰`, orders of magnitude beyond a one-second budget. The pairs are also discovered in arbitrary order, so you'd have to sort the collected pairs at the end anyway — meaning you pay for sorting and the quadratic scan.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [-520, -470, -20, 30]Array state
(-520,-470)
diff 50 → best
-520 -470 -20 30C · Code with teaching comments
Reference implementation previewpublic List<Integer> closestNumbers(int[] arr) { int best = Integer.MAX_VALUE; List<int[]> pairs = new ArrayList<>(); for (int i = 0; i < arr.length; i++) { for (int j = i + 1; j < arr.length; j++) {Explore the full codeHide the full code
D · Why it works and complexityO(n²) timeO(1) plus output spaceOpen the invariant and proofExplore the proofHide the proof
The quadratic blow-up comes from comparing far-apart elements that can never be the closest pair. Sorting removes exactly those useless comparisons.
ComplexityO(n²) time, O(1) plus output space — n(n−1)/2 pair comparisons ≈ n²/2; for n = 2·10⁵ that is ~2·10¹⁰ operations — far too slow.
E · Edge cases and pitfalls4arr = [3, 3] — Difference 0 — single pair (3, 3), the global minimum since 0 cannot be beaten.Explore edge casesHide edge cases
Edge cases handled
arr = [3, 3]Difference 0 — single pair (3, 3), the global minimum since 0 cannot be beaten.
Pitfalls
- Keeping only one 'best pair' variable — silently drops tied pairs.
- Forgetting to sort the collected pairs at the end — they are found out of order.
- Quadratic time times out at n = 2·10⁵.
Approach 2 of 2 · Optimal
Sort + Adjacent Scan (Optimal)
1Hint 1Explore hintHide hint
If the points were on a number line in order, where could the two closest ones possibly be relative to each other?
2Hint 2Explore hintHide hint
Sort the array. The minimum difference must occur between two CONSECUTIVE sorted elements — anything non-adjacent has an element between them that is closer.
3Hint 3Explore hintHide hint
First pass: compute the minimum adjacent gap. Second pass: emit every adjacent pair whose gap equals that minimum. Both passes are O(n).
A · Core idea
Sort the array ascending. Now claim: the globally closest pair is adjacent in this order. Proof in one line — suppose the closest pair is a[i] and a[k] with k > i + 1; then a[i+1] sits between them, so a[i+1] − a[i] ≤ a[k] − a[i], giving an adjacent pair at least as close. Hence we only ever inspect neighbours.
Why two passes. A single left-to-right pass cannot emit pairs as it goes, because it doesn't yet know the global minimum gap — an even smaller gap might appear later, which would invalidate everything emitted so far. So pass one computes min_gap = min(a[i+1] − a[i]); pass two walks the same neighbours and collects every pair with a[i+1] − a[i] == min_gap.
Why the output is already ordered. Because we scan the sorted array left to right, pairs come out in ascending order and each pair is naturally (smaller, larger) — no post-sort needed, unlike brute force.
Why differences are safe. After sorting, a[i+1] − a[i] ≥ 0, so we use the plain signed subtraction and never need abs. The maximum gap (2·10⁷) fits in a 32-bit int.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
arr = [-520, -470, -20, 30]Array state
gaps
50, 450, 50 → min = 50
-520 -470 -20 30C · Code with teaching comments
D · Why it works and complexityO(n log n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Sorting is a pre-processing trick that converts a global, all-pairs question into a local, neighbours-only question. The same 'sort then look at adjacent elements' move solves Maximum Gap, Merge Intervals, and Meeting Rooms.
ComplexityO(n log n) time, O(n) space — Sorting is O(n log n) and dominates; the two linear scans are O(n). Output storage is O(n) in the worst case (e.g. an arithmetic progression where every adjacent pair ties).
E · Edge cases and pitfalls5arr = [5, 4, 3, 2] — Sorted [2,3,4,5], all gaps 1 → every adjacent pair ties: 2 3 3 4 4 5.Explore edge casesHide edge cases
Edge cases handled
arr = [5, 4, 3, 2]Sorted [2,3,4,5], all gaps 1 → every adjacent pair ties: 2 3 3 4 4 5.arr = [1, 1, 5]Sorted [1,1,5], gap (1,1)=0 is the minimum → output 1 1.
Pitfalls
- Trying to emit pairs in a single pass before the global minimum is known.
- Reporting only the first minimal pair instead of all ties.
- Using abs() on already-sorted neighbours (harmless but signals you missed that the gap is non-negative).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic List<Integer> closestNumbers(int[] arr) { Arrays.sort(arr); int minGap = Integer.MAX_VALUE; for (int i = 0; i + 1 < arr.length; i++) { minGap = Math.min(minGap, arr[i + 1] - arr[i]);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Stopping at the first minimal pair
Multiple pairs can share the smallest gap (e.g. an arithmetic run). Returning on the first match drops the rest.
Explore the code comparisonHide the code comparison
Stopping at the first minimal pair
Multiple pairs can share the smallest gap (e.g. an arithmetic run). Returning on the first match drops the rest.
Don't write this
for i in range(len(a) - 1):
if a[i + 1] - a[i] == min_gap:
return [a[i], a[i + 1]]Write this instead
for i in range(len(a) - 1):
if a[i + 1] - a[i] == min_gap:
out += [a[i], a[i + 1]]
return out2Collecting pairs before knowing the minimum
A later, smaller gap invalidates pairs you already emitted. You must compute min_gap fully (pass 1) before collecting (pass 2).
Explore the code comparisonHide the code comparison
Collecting pairs before knowing the minimum
A later, smaller gap invalidates pairs you already emitted. You must compute min_gap fully (pass 1) before collecting (pass 2).
Don't write this
best = a[1] - a[0]
out = [a[0], a[1]]
for i in range(1, len(a) - 1):
g = a[i + 1] - a[i]
if g <= best:
best = g
out += [a[i], a[i + 1]]Write this instead
min_gap = min(a[i + 1] - a[i] for i in range(len(a) - 1))
out = []
for i in range(len(a) - 1):
if a[i + 1] - a[i] == min_gap:
out += [a[i], a[i + 1]]Revise
Carry the pattern into the interview
Pattern to remember
Sort, then scan adjacent pairs for the minimum gap
Code pattern to memorize
a = sorted(arr)
min_gap = min(a[i+1] - a[i] for i)
for i: if a[i+1] - a[i] == min_gap: emit a[i], a[i+1]Rules to remember
- 1After sorting, the closest pair is ALWAYS adjacent — you never need to compare non-neighbours.
- 2Do two passes: first find
min_gap, then collect all pairs equal to it. One pass can't know the minimum until it finishes. - 3There can be multiple pairs tied for the minimum — output all of them, in ascending order.
- 4Within each pair print the smaller value first; pairs already come out ascending because the array is sorted.
- 5Differences can be large; values may be negative. Use the signed difference
a[i+1] - a[i](non-negative after sort), not unsigned arithmetic.
Use this pattern when
- You need the closest pair(s) by value over an unordered list
- The notion of 'closeness' is 1-D distance on a number line
- Ties must all be reported, not just one representative pair
- Input is plain integers/reals where sorting is cheap
Choose another pattern when
- Closest pair in 2-D / k-D space → that is the divide-and-conquer closest-pair-of-points problem, not this
- You only need the minimum gap value, not the pairs → skip the second pass
- Stream is infinite / cannot be sorted → needs a balanced BST or order-statistics structure
Interview takeaway
Sorting collapses an all-pairs question (O(n²) comparisons) into an adjacent-neighbour scan (O(n)) — whenever 'closest by value' appears, sort first and look only at neighbours.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternSort-then-scan-neighbours. When 'closest by value' or 'smallest gap' appears over a 1-D list, sorting makes the answer adjacent, turning O(n²) all-pairs into an O(n) neighbour pass. Same shape as Maximum Gap and Minimum Absolute Difference.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Maximum GapComing soonSame sort-then-neighbours idea, but take the maximum adjacent gap; bucket/radix sort gives O(n).
- Minimum Absolute Difference (LeetCode 1200)Coming soonIdentical algorithm — sort, scan neighbours, collect all minimal-difference pairs.
- Closest Pair of Points (2-D)Coming soonThe 2-D generalisation needs divide-and-conquer with a strip check — sorting alone is not enough.