75. Sort Colors — DSA Atlas

MediumTwo PointersTwo pointers (three-way partition)Dutch National Flag partition

Sort Colors

Given an array nums with n objects colored red, white, or blue and represented by the integers 0, 1, and 2, sort them in-place so that objects of the same color are adjacent, in the order red (0), white (1), then blue (2). You must solve it without using the library sort function.

Open official problem prompt ↗

In plain English

Rearrange an array of 0s, 1s, and 2s into sorted order in a single pass, mutating the array in place.

Picture it like this

Sorting a mixed pile of red, white, and blue socks by hand: red socks go to the far left, blue socks to the far right, and whites naturally settle in the middle as you sweep across the pile once.

Example

Input: nums = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]
Why: The two 0s come first, then the two 1s, then the two 2s.

Constraints

n == nums.length1 <= n <= 300nums[i] is either 0, 1, or 2Follow-up: solve in one pass with O(1) extra space

Pattern lesson

See the pattern, then code

Dutch National Flag partition

↗

Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Keep three regions with a low, mid, and high pointer: everything before low is 0, everything after high is 2, and the middle is being scanned. Route each value scanned by mid into its region.

New words, made simpleKnow these before the algorithm

In-place: The array is reordered using only a constant amount of extra memory, no second array.
Three-way partition: Splitting elements into three regions (less than, equal to, greater than a pivot) in one scan.
Invariant region: A contiguous slice of the array already known to hold only one value.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Counting sort (two pass)

Correct and simple, but it scans the data twice and does not meet the one-pass follow-up.

Count how many 0s, 1s, and 2s appear, then overwrite the array with that many of each in order.

Time O(n)Space O(1)

Best choiceDutch National Flag (one pass)

Single pass, constant space, and self-contained — the intended optimal answer.

Maintain low, mid, high pointers that carve the array into a 0-region, an unscanned middle, and a 2-region; route each scanned value to its region.

Time O(n)Space O(1)

The rule we keep true

Invariant

At all times nums[0:low] are all 0, nums[low:mid] are all 1, nums[high+1:] are all 2, and nums[mid:high+1] is still unprocessed.

Why this is correct

Reasoning

Every iteration classifies exactly one new element and shrinks the unprocessed window nums[mid:high+1]. A value of 2 must be moved from high (unknown) back into mid, so mid cannot advance after that swap; 0s and 1s are already scanned, so mid advances. When mid passes high, no unprocessed elements remain and the three invariant regions cover the whole array.

The algorithm in three movesSay these aloud before coding

1Set low = mid = 0 and high = len(nums) - 1

low=0 mid=0 high=5, nums[mid]=2 -> swap with high

2While mid <= high, inspect nums[mid]

[0,0,2,1,1,2] low=1 mid=1 high=4

3If 0, swap with low and advance both low and mid

final [0,0,1,1,2,2]

4If 1, just advance mid

5If 2, swap with high and only shrink high (do not advance mid)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readnums[mid]=2

2 · AskWhere does a 2 belong?

3 · Update statelow=0 mid=0 high=5

4 · ResultSwap nums[0] and nums[5] -> [0,0,2,1,1,2], high=4

Key takeaway

mid starts at index 0 and high at index 5; the first value 2 is swapped toward the tail.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initialize the three pointers
low and mid begin at the front; high begins at the last index so the 2-region grows from the right.
2
Lines 4Loop until the middle is empty
Processing continues while there is still an unclassified element (mid <= high).
3
Lines 5-8Handle a 0
Swap it into the 0-region and advance both low and mid because the swapped-in value came from mid and is already scanned.
4
Lines 9-10Handle a 1
A 1 is already in its final region, so only mid moves forward.
5
Lines 11-13Handle a 2
Swap it to the 2-region and shrink high; mid stays put because the value pulled in from high has not been examined yet.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-element array
Array already sorted
Array containing only one color
All values equal to 2 (every step shrinks high)

Common beginner mistakes

Advancing mid after swapping a 2 to high — the newly pulled value is unexamined and could be another 2 or a 0
Using a for-loop over a fixed range instead of a while-loop, which breaks once mid stops advancing
Using low <= high or mid < high as the loop guard, which drops the final element

Check your understanding

Why do we advance mid when we place a 0 but not when we place a 2?

Sort Colors

Sort Colors

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two Pointers