Sort Colors ​
Sort an array containing only 0s, 1s and 2s in place, in a single pass and without using a sorting library. Also known as the Dutch National Flag problem.
Approach ​
2 approaches: Count the number of occurrences of each color, overwrite the array -> Called bucket sort.
Approach 2: Keep two pointers left and right. Start another pointer i from left till i > right. When nums[i] = 0, swap with left. Increment both iand left. When nums[i] = 2, swap with right, but only decrement right. don't change i because we could've swapped with i with 0, and there is a 1 on the left of i. In next iteration, 0 will get swapped to left.
Remarks ​
First approach is easy to come up with and I figured it out.
Second was a bit more harder