Sort Colors

Problem

An array nums contains only the values 0, 1, and 2, representing three colors. Rearrange the array in place so that all 0s come first, then all 1s, then all 2s, without calling a library sort. The target is a single pass over the array using constant extra memory.

• nums has between 1 and 500 elements.
• Every element is 0, 1, or 2; any of the three may be absent entirely.

Examples

• nums = [1, 2, 0, 0, 2, 1, 2] → [0, 0, 1, 1, 2, 2, 2].
• nums = [2, 1, 0] → [0, 1, 2]. One of each, in reverse order.
• nums = [2, 2, 2, 2, 1, 1] → [1, 1, 2, 2, 2, 2]. No zeros at all; the algorithm must not depend on every color being present.

Hints

1. With only three values, you could count them and overwrite the array. Why might the interviewer reject that, and what constraint is it violating?
2. Partitioning around a pivot moves elements to one of two sides. Can you maintain three regions at once?
3. Dutch national flag: pointers low, mid, high; everything before low is 0, everything after high is 2, mid scans the unknown middle.