← Pointer Manipulation

Micro-Drill #10 — Dutch flag (3-way partition)

Pointer Manipulation Target: 15s

Three-way partition handles duplicates efficiently. Classic for sort-colors type problems.

lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
    if a[mid] < pivot:
        a[lo], a[mid] = a[mid], a[lo]
        lo += 1; mid += 1
    elif a[mid] == pivot:
        mid += 1
    else:
        a[mid], a[hi] = a[hi], a[mid]
        hi -= 1

Type it from memory. Go.

Practice Problems

• 75. Sort Colors
• 324. Wiggle Sort II

Related Coding Drills

• Drill #33 — Dutch national flag (3-way partition) Medium
• Drill #31 — Quick sort (Lomuto partition) Medium