The array holds only 0s, 1s and 2s, like red, white and blue. Sort it in place, in a single pass, without a library sort.
DSA Animator › DSA Revision › Arrays › Sort Colors
Remember: three pointers split the array into 0s, unknown, and 2s. After swapping with high, check mid again. The video solves Sort Colors (LeetCode 75, Medium) with the Dutch National Flag pattern from the Arrays topic, and you can replay every step in the interactive Sort Colors animation.
The array holds only 0s, 1s and 2s, like red, white and blue. Sort it in place, in a single pass, without a library sort.
For 2, 0, 2, 1, 1, 0, the sorted result is 0, 0, 1, 1, 2, 2.
Counting the colours and rewriting the array takes two passes. A general sort is O of n log n. We can do it in one pass, with O of 1 space.
Keep three pointers: low, mid and high. Everything before low is 0, and everything after high is 2. Mid scans the unknown part in between. A 0 swaps with low and both move, a 2 swaps with high and only high moves, and a 1 just moves mid.
Mid sees a 2: swap it to the end, and high moves left. Now mid sees a 0: swap with low, and both move. Another 0: swap, and both move again. Mid sees a 2: swap it with high, and high moves left. Then a 1: mid just moves on. Another 1, and mid passes high, so we stop. The array is sorted in one pass.
In code, loop while mid is not past high. A 0 swaps with low, and both low and mid move forward. A 2 swaps with high, and only high moves back, because the swapped-in value is still unchecked. A 1 only moves mid, so it's O of n time and O of 1 space.
Remember: three pointers split the array into 0s, unknown, and 2s. After swapping with high, check mid again.