Dutch National Flag (Sort 0/1/2)

    DSA · Intermediate

    Definition

    Three pointers partition an array of 0s, 1s and 2s in a single pass.

    Teaches in-place partitioning used inside quick sort.

    Diagram

    [2 0 1 2 0]→ [0 0 1 2 2]

    Flowchart

    low = mid = 0, high = n−10 → swap with low, move both1 → move mid2 → swap with high, move high

    Example: Sort colors

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

    Output: [0, 0, 1, 2, 2]

    Complexity

    O(n) time · O(1) space

    Key points

    • Do not move mid after swapping with high
    • One pass only

    Interview questions

    Why not increment mid after swapping with high?

    The swapped-in value has not been checked yet.

    More DSA topics

    ArraysLinked ListStackQueue