Sort Colors
Problem
An array contains only the values 0, 1 and 2, standing for three colours. Sort it in place so all 0s come first, then 1s, then 2s, without using a library sort. Try to do it in a single pass.
Examples
Constraints
- • 1 <= nums.length <= 300
- • nums[i] is 0, 1 or 2
Hints & approach
Hint 1
Counting the three values and rewriting takes two passes.
Hint 2
For one pass, grow a region of 0s from the left and a region of 2s from the right.
Hint 3
Do not advance the scanning pointer after swapping with the right side; the swapped-in value is unchecked.
Approachtry the hints first
Use the Dutch national flag partition with three pointers: low (next slot for 0), mid (current element) and high (next slot for 2). If nums[mid] is 0, swap it with nums[low] and advance both low and mid. If it is 1, just advance mid. If it is 2, swap it with nums[high] and decrement high without moving mid, since the value brought in has not been examined. Stop when mid passes high.
Time O(n) · Space O(1)