LeetCode 75 · Two pointers

Sort Colors (Dutch flag), explained with a picture

Sorting red, white and blue marbles.

Two pointers
▶ Watch it step by step

The problem

Sort a list of 0s, 1s and 2s (red, white, blue) in one pass and in place.

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

Picture it

Picture marbles being sorted into three zones by three pointers: left of lo is red, between lo and mid is white, right of hi is blue. mid scans the unknown middle: red swaps to the lo zone, blue swaps to the hi zone, white just moves on.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Dutch national flag: three pointers, one pass. O(n), O(1).

Python solution

def sort_colors(a):          # 0 red, 1 white, 2 blue
    lo, mid, hi = 0, 0, len(a) - 1
    while mid <= hi:
        if a[mid] == 0:
            a[lo], a[mid] = a[mid], a[lo]
            lo, mid = lo + 1, mid + 1
        elif a[mid] == 1:
            mid += 1
        else:
            a[mid], a[hi] = a[hi], a[mid]
            hi -= 1
    return a

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.