The hints on below the problem have suggested a two-pass solution.
Now I will focus on the one-pass solution.
The one-pass solution has no mystery. Just swap all 0's to the left and all 2's to the right and the 1's will automatically fall in the middle.
Now comes the following code. You may play with it using some examples on a paper to see how it works.
1 void sortColors(vector<int>& nums) { 2 int red = 0, blue = nums.size() - 1; 3 for (int i = 0; i <= blue; i++) { 4 while (nums[i] == 2 && i < blue) 5 swap(nums[i], nums[blue--]); 6 while (nums[i] == 0 && i > red) 7 swap(nums[i], nums[red++]); 8 } 9 }
