Abstract / Summary

Given a list of integers, find the smallest difference between any two numbers in the list.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 75% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding all pairs of integers in an input list whose absolute difference is minimal. The algorithm proceeds by first sorting the input, then scanning the sorted sequence to compute differences between consecutive elements. While scanning, it maintains the smallest difference seen so far and a collection of pairs that achieve this difference. Finally, it returns the pairs in sorted order.

Key Steps

Sorting the Input

The first operation arranges the numbers in non-decreasing order, which guarantees that the absolute difference between any two elements is simply the difference of the later element minus the earlier one.

arr.sort()

Initializing Tracking Variables

Two variables are prepared before the scan: low holds the smallest difference encountered, initialized to positive infinity, and result stores the pairs that realize this difference.

low = inf
result = []

Scanning Adjacent Pairs

A single forward loop examines each adjacent pair in the sorted list. For each index i from 1 to the last element, the algorithm extracts the two neighboring values, computes their difference, and updates the tracking variables accordingly.

for i in range(1, len(arr)):
    a = arr[i - 1]
    b = arr[i]
    diff = b - a
    if   diff <  low:
        result = [ [ a, b ] ]
        low = diff
    elif diff == low:
        result.append([ a, b ])

Returning the Result

After the loop finishes, the list of pairs is sorted to ensure a deterministic order before being returned.

return sorted(result)

Edge Cases Handled

When the input list contains duplicate values, the sorting step places identical numbers next to each other, producing a difference of zero. The algorithm correctly records this as the minimal possible difference and includes all adjacent duplicate pairs.

If the list has only two elements, the loop executes exactly once, computes the single difference, and returns that pair as the sole result.

An empty list or a list with a single element would result in the loop body never executing; the function would return an empty list, which aligns with the expectation that no pairs exist.

Performance Optimizations

The most significant optimization is the reliance on sorting followed by a single linear scan. Sorting transforms the problem of comparing every possible pair (quadratic work) into a linear pass over adjacent elements, because the minimal absolute difference must occur between neighbors in a sorted sequence.

Using inf as the initial sentinel for low avoids the need for a separate pass to establish an initial difference value.

The update logic replaces the entire result list only when a new smaller difference is found, which prevents unnecessary accumulation of pairs that are later discarded.

Finally, the call to sorted(result) at the end operates on a list whose size is bounded by the number of adjacent pairs that share the minimal difference, which is typically much smaller than the original input size. This ensures that the final ordering step does not dominate the overall runtime.

Imagine you have a big pile of numbered blocks scattered all over the floor. To solve this puzzle, the first step is to line all the blocks up in a perfect row from the smallest number to the biggest number, just like beads on a string. Once they are in a nice line, neighbors sit right next to each other. Taking two neighbors and finding the difference between their numbers is like measuring the tiny gap between them.

The goal is to find which neighbors are the absolute closest together. You walk down the line, checking every single pair of neighbors one by one. You keep a secret note of the smallest gap found so far. Whenever you find a gap that is narrower than the one you previously noted, you throw away your old list and start a new one with this better pair. If you find another pair that has the exact same tiny gap as your best one, you just invite them to join the list too. By the time you reach the end of the line, you have a perfect collection of all the pairs that are closer than anyone else.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go		Rust	TS
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	everthis			JS
	fartem						Ruby
	fpdjsns	C++
	fsq	C++
	Garvit244		Python
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	suxrobGM					C#
	varunu28				Java
	withaarzoo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality