Abstract / Summary

Check if the difference between each pair of consecutive numbers is the same.

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 69% (400k+ 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 determines whether a given integer array can be rearranged to form an arithmetic progression. It follows a straightforward strategy: sort the input, compute the common difference from the first two elements, and verify that every consecutive pair respects this difference. The function returns a Boolean result indicating success or failure.

Key Steps

The algorithm consists of three distinct operations, each reflected in a concise code fragment.

Sorting the input establishes a deterministic order that makes the progression check trivial.

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

After sorting, the common difference is derived from the first two elements. The use of auto lets the compiler infer the appropriate signed integer type.

auto diff = arr[1] - arr[0];

A forward scan validates the progression. The loop starts at the third element and compares each adjacent difference to the previously computed diff. An early return aborts the scan as soon as a mismatch is detected.

for (auto i = 2; i < arr.size(); i++)
    if (arr[i] - arr[i-1] != diff)
        return false;

If the loop completes without triggering the early exit, the function concludes that the array can indeed be arranged as an arithmetic progression.

return true;

Edge Cases Handled

The implementation gracefully accommodates several boundary conditions:

• Already Sorted Input - When the input is pre-sorted, the sort call incurs minimal overhead, and the subsequent difference checks operate directly on the original order.
• Uniform Elements - If all elements are identical, the computed diff equals zero, and each subsequent subtraction yields zero, satisfying the progression condition.
• Negative Numbers - The subtraction logic works uniformly for negative values, allowing progressions that decrease or cross zero.
• Single-Element or Empty Arrays - Although the function accesses the first two elements, the typical problem definition guarantees at least two numbers. In contexts where the array length is one or zero, the logical definition of an arithmetic progression holds trivially, and the loop body would never execute, leading to a true result.

Performance Optimizations Observed

The code leverages several language and library features that contribute to efficient execution:

• Standard Library Sort - std::sort implements introsort, a hybrid algorithm that combines quicksort, heapsort, and insertion sort. This choice provides fast average-case performance while guarding against pathological inputs.
• Early Termination - The moment a discrepancy is found, the function returns false. This prevents unnecessary comparisons in non-progressive arrays, especially when the violation occurs early.
• Reference Parameter - The input vector is passed by non-const reference, avoiding a copy of the entire container and allowing the in-place sort to operate directly on the caller’s data.
• Type Inference with auto - Using auto for the loop index and the difference variable eliminates explicit type specifications, letting the compiler generate the most efficient native type for the platform.

Collectively, these choices ensure that the routine runs with minimal overhead while maintaining clear and maintainable code.

Imagine you have a big pile of numbered building blocks scattered all over the floor. To solve this puzzle, the first step is to line up all those blocks from the smallest number to the biggest number, just like putting your toys in a neat row. Once they are all in order, think about the space between each block. For a sequence to be special, the distance or the number of empty spots between every single block must be exactly the same. You start by looking at the first two blocks to see how far apart they are. Then, you walk down the line and check every other pair of blocks. If you ever find a pair that is a different distance apart than the first pair, it means the pattern is broken, and it is not the special sequence you are looking for. If you make it all the way to the end and every jump between blocks is the same size, then you found the pattern.

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++
	leetcode.ca	C++	Python		Java		JS	Go	C	Rust	TS
	Progiez	C++	Python		Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim								C
	fartem					Ruby
	FelixFan1122			C#
	fsq	C++
	JoshCrozier						JS
	keineahnung2345	C++
	lkwq007		Python
	muhammadfarhankt							Go
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C, C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
fartem	Ruby
FelixFan1122	C#
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
trung-hn	Python
varunu28	Java
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