Dutch National Flag
Problem Description
Given an array A and an index pivot_idx, rearrange A such that all elements less than A[pivot_idx] (the pivot value) come first, followed by all elements equal to the pivot, and finally all elements greater than the pivot. This must be done in-place.
Solution Approach
Let
A = [0, 1, 2, 0, 2, 1, 1]
pivot_idx = 1
pivot_value = A[pivot_idx] = 1
We maintain three pointers (our “fingers”):
smaller: end of the “LESS THAN pivot” zone.
Anything to its left is < pivot_value.
Starts at 0.
equal: the current “inspector” pointer.
Points to the element under examination.
Starts at 0.
larger: start of the “GREATER THAN pivot” zone (from the right end).
Anything at or to its right is > pivot_value.
Starts at len(A) (one past the end).
A[0...smaller-1] = LESS zone (empty)
A[smaller...equal-1] = EQUAL zone (empty)
A[equal...larger-1] = UNCLASSIFIED (the whole array)
A[larger...end] = GREATER zone (empty)
We loop while equal < larger:
while equal < larger:
if A[equal] < pivot_value:
swap(A[smaller], A[equal])
smaller += 1
equal += 1
elif A[equal] == pivot_value:
# Already in the EQUAL zone
equal += 1
else: # A[equal] > pivot_value
larger -= 1
swap(A[equal], A[larger])
# do not increment `equal`!
Step-by-Step Walkthrough
Iteration | smaller | equal | larger | A | Action |
|---|---|---|---|---|---|
1 | 0 | 0 | 7 | [0, 1, 2, 0, 2, 1, 1] | A[0]=0 < 1: swap(0↔0), smaller=1, equal=1 |
2 | 1 | 1 | 7 | [0, 1, 2, 0, 2, 1, 1] | A[1]=1 == 1: equal=2 |
3 | 1 | 2 | 7 | [0, 1, 2, 0, 2, 1, 1] | A[2]=2 > 1: larger=6; swap(A[2], A[6]) → [0, 1, 1, 0, 2, 1, 2] |
4 | 1 | 2 | 6 | [0, 1, 1, 0, 2, 1, 2] | A[2]=1 == 1: equal=3 |
5 | 1 | 3 | 6 | [0, 1, 1, 0, 2, 1, 2] | A[3]=0 < 1: swap(A[1], A[3]) → [0, 0, 1, 1, 2, 1, 2]; smaller=2, equal=4 |
6 | 2 | 4 | 6 | [0, 0, 1, 1, 2, 1, 2] | A[4]=2 > 1: larger=5; swap(A[4], A[5]) → [0, 0, 1, 1, 1, 2, 2] |
7 | 2 | 4 | 5 | [0, 0, 1, 1, 1, 2, 2] | A[4]=1 == 1: equal=5 |
Stop | — | 5 | 5 | [0, 0, 1, 1, 1, 2, 2] | equal == larger → loop ends |
Final partition:
LESS (A[0...1]): [0, 0]
EQUAL (A[2...4]): [1, 1, 1]
GREATER (A[5...6]): [2, 2]
Code
Check leet code
Complexity Analysis
Time: Each element is examined at most once and swapped at most once → O(n). Space: In-place partitioning → O(1) extra space.
Notes & Learnings
Key insight: when swapping a “greater” element to the right, don’t advance equal—you must re-examine the swapped-in element.
(Key takeaways, patterns, common pitfalls, related problems)