Abstract / Summary

Given a list of integers, find the largest difference between any two adjacent elements after sorting 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 53% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Bucket Sort
• Radix Sort
• 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 defines a class Solution with a single public method maximumGap. The method receives a mutable reference to a vector of integers and returns the largest difference between any two successive elements after the vector is ordered. The algorithm follows a straightforward three-stage process: a trivial size check, sorting the entire collection, and a linear scan to locate the maximum adjacent gap.

Size Check

The first conditional guards against the degenerate case where the input contains only one element. In such a scenario there are no pairs of distinct elements, so the function returns zero immediately.

if (nums.size() == 1)
    return 0;

This early exit prevents the overhead of sorting and scanning when the result is predetermined.

Sorting Phase

The core of the algorithm relies on arranging the numbers in non-decreasing order. The standard library sort function is invoked, which employs an introspective sort combining quicksort, heapsort, and insertion sort. This choice leverages a highly tuned implementation that adapts to the data distribution and size, delivering strong practical performance.

sort(nums.begin(), nums.end());

By sorting in place, the method avoids additional memory allocations, keeping the footprint minimal.

Linear Scan for Maximum Gap

After ordering, the method iterates once over the vector, starting from the second element. For each position it computes the difference with its predecessor, updates a running maximum when a larger gap is encountered, and finally returns that maximum.

int result = 0;
for (int i = 1; i < nums.size(); i++)
{
    auto diff = nums[i] - nums[i - 1];
    if (result < diff)
        result = diff;
}
return result;

The use of auto for the temporary diff variable lets the compiler infer the appropriate type, which can aid in generating efficient machine code. Maintaining a single result variable eliminates the need for auxiliary data structures, ensuring the scan runs with constant extra space.

Edge Cases Handled

The implementation gracefully handles several boundary conditions without explicit checks. When the input vector is empty, the size check does not trigger, but the subsequent loop body never executes because the loop condition i < nums.size() fails immediately. Consequently, result remains zero and the method returns zero, which is a sensible default for an empty collection. Duplicate values are also accommodated; the computed difference becomes zero for equal adjacent elements, and the maximum gap reflects the largest separation among distinct values, if any exist.

Performance Optimizations

The code exhibits a few deliberate choices that contribute to efficient execution. The early return for a single-element vector eliminates unnecessary work for the simplest case. Leveraging the standard sort routine provides a highly optimized sorting path that adapts to the input characteristics, reducing the number of comparisons and swaps compared to a naïve implementation. The subsequent linear scan uses a minimal set of operations: a single subtraction, a comparison, and a conditional assignment per iteration. By keeping all work within the original vector and avoiding extra containers, the method minimizes cache pressure and memory traffic, which is beneficial for large inputs. The straightforward control flow also enables the compiler to apply aggressive inlining and loop unrolling where appropriate.

Imagine you have a big pile of numbered building blocks scattered all over the floor. To solve this puzzle, the first thing the code does is put all those blocks in a straight line, starting from the smallest number and ending with the biggest one. It is just like lining up your toys from shortest to tallest.

Once every block is in its correct spot, the code looks at each pair of neighbors sitting right next to each other. It measures the space between each pair, which is just the difference between the two numbers. It keeps track of the biggest gap it finds while it walks along the line. By the time it reaches the end of the blocks, it knows exactly which gap between two numbers was the largest one, just like finding the widest space in your line of toys.

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			C#		Java	Go
	LeetcodeHelp	C++	Python					Java
	MemoryLimitExceeded	C++
	Progiez	C++	Python					Java
github	aylei			Rust
	begeekmyfriend						C
	black-shadows	C++
	charles-wangkai							Java
	chenyanzhe	C++
	everthis				JS
	fsq	C++
	gaosq0604		Python
	halfrost								Go
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	lennylxx						C
	linouk23		Python
	lkwq007		Python
	lzl124631x	C++
	MacJim	C++
	ruoru			Rust
	shreymehul					C#
	suxrobGM					C#
	wisdompeak	C++
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	C++
Progiez	C++, Java, Python
aylei	Rust
begeekmyfriend	C
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fsq	C++
gaosq0604	Python
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lennylxx	C
linouk23	Python
lkwq007	Python
lzl124631x	C++
MacJim	C++
ruoru	Rust
shreymehul	C#
suxrobGM	C#
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

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