Abstract / Summary

Given an array and a pivot, rearrange the array so elements smaller than the pivot come first, then elements equal to the pivot, then elements larger than the pivot.

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 91% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Simulation
• Two Pointers

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 method that rearranges an input list of integers around a specified pivot value. The algorithm separates the original elements into three groups-those smaller than the pivot, those equal to the pivot, and those larger than the pivot-preserving the original relative order within each group. After classification, the three groups are concatenated to produce the final reordered list.

Core Logic

Initialization of Buckets

Three auxiliary containers are created to hold the three categories of numbers. Each container is an empty list ready to receive elements during the scan of the input.

low  = []
same = []
high = []

Single-Pass Classification

The method iterates over every element in the input list exactly once. For each element, a three-way conditional determines the appropriate bucket:

• If the element is less than the pivot, it is appended to the low bucket.
• If the element is greater than the pivot, it is appended to the high bucket.
• Otherwise (the element equals the pivot), it is appended to the same bucket.

for n in nums:
    if   n < pivot:
        low .append(n)
    elif n > pivot:
        high.append(n)
    else:
        same.append(n)

The use of append ensures that elements are stored in the order they appear in the original list, thereby maintaining stability within each partition.

Concatenation of Results

After the loop finishes, the three buckets are combined using the + operator, which produces a new list containing the elements of low, followed by same, and finally high. This step yields the final pivot-ordered array.

return low + same + high

Edge Cases Handled

When the input list is empty, the three buckets remain empty and the concatenation returns an empty list, correctly reflecting the absence of data.

If every element is smaller than the pivot, all values accumulate in the low bucket while same and high stay empty; the concatenation returns a list identical to the original order, which is the expected outcome.

Conversely, when all elements are larger than the pivot, they are collected in high, and the result consists solely of that bucket, preserving the original sequence.

When all elements equal the pivot, they are placed in same; the final list is a direct copy of the input, again preserving order.

The algorithm also gracefully handles duplicate values across the three categories, negative numbers, and very large integers because the comparisons are straightforward integer operations without any special casing.

Performance Optimizations

The design achieves a linear traversal of the input, meaning each element is examined exactly once. By using three separate lists and appending directly, the method avoids costly element shifting or repeated scanning.

Appending to a Python list is an amortized constant-time operation, so the accumulation of elements into the buckets does not introduce hidden overhead.

The final concatenation leverages Python’s list addition, which creates a new list sized to hold the combined elements in a single allocation. This approach eliminates the need for incremental extensions or repeated copying, resulting in efficient memory usage for the output.

Overall, the implementation balances clarity with a streamlined execution path, ensuring that the pivot reordering is performed with minimal computational waste.

Imagine you have a big messy pile of building blocks lying on the floor. You want to sort these blocks based on a special number called the pivot. To do this, you get three empty buckets. The first bucket is for blocks that are smaller than the pivot number. The second bucket is for blocks that are exactly the same size as the pivot. The third bucket is for all the blocks that are bigger than the pivot.

You pick up each block from the pile one by one and look at it. If the block is little, you drop it into the first bucket. If the block is exactly the same as the pivot, you put it in the middle bucket. If the block is bigger, it goes into the last bucket. Once every single block is tucked away in its own bucket, you line the buckets up in a row. First comes the bucket with the little blocks, then the bucket with the matching blocks, and finally the bucket with the big blocks. Now all the blocks are neatly sorted in a line.

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

Time: linear
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++		Java		Python				TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++	JS	Java		Python			Go	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	Shamik07						Dart
	suxrobGM							C#
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
Shamik07	Dart
suxrobGM	C#
varunu28	Java
withaarzoo	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