Two PointersTwo Pointers
Partitioning (Dutch National Flag)
Rearrange an array in place so that elements less than, equal to, and greater than a pivot occupy contiguous regions, using pointers that mark region boundaries.
2
0
↑lo↑mid
0
1
2
2
1
3
1
4
0
5
0
6
2
7
1
8
0
9
↑hi
1/12Three regions: a[0..lo) are 0s, a[lo..mid) are 1s, a(hi..n) are 2s, and a[mid..hi] is unknown. Initially everything is unknown.
lo (end of 0s)mid (current)hi (start of 2s)Placed 0 / 2Swapped
PseudocodeLearn Partitioning →
1lo = 0, mid = 0, hi = n - 12while mid <= hi:3 if a[mid] == 0: swap(a[lo], a[mid]); lo++; mid++4 elif a[mid] == 1: mid++5 else: swap(a[mid], a[hi]); hi--Variables
lo0
mid0
hi9
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed