Given an array nums with n objects colored red (0), white (1), or blue (2), sort them in-place so that objects of the same color are adjacent, in the order red, white, and blue. You must solve this without using the library's sort function.
nums = [2,0,2,1,1,0][0,0,1,1,2,2]Invariant: [0..lo-1] all 0s, [lo..mid-1] all 1s, [hi+1..n-1] all 2s. When mid sees 0, swap with lo (known 1) — both advance. When 2, swap with hi (unknown) — only hi shrinks since new value at mid is unclassified. When 1, just advance mid.
Counting the colours and rewriting the array takes two passes. A general sort is O(n log n). We can do it in one pass, with O(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.
Three pointers split the array into 0s, unknown, and 2s. After swapping with high, check mid again.
Run the animation above on your own input, or watch the 1:27 video explanation of Sort Colors with a dry run and Java code.