4ms C++ solution with one pass


  • 7
    A

    Maintain the tail index for red region, and head index for the blue region. Scan the whole array, and swap the current element with either red tail or blue head respectively.

      class Solution {
        public:
            void sortColors(vector<int>& nums) {
                int tail_red = 0;
                int head_blue = nums.size() - 1;
                int cur = 0;
                while( cur <= head_blue){
                    if(nums[cur] == 0){
                        swap(nums[tail_red], nums[cur]);
                        tail_red ++;
                        cur ++;
                    }else if (nums[cur] == 2){
                        swap(nums[head_blue], nums[cur]);
                        head_blue = head_blue - 1;
                    }else
                        cur ++;
                }
            }
        };

  • 0
    W

    You need to check either the cur is bigger than head blue before the swapping


  • 0

    Thank your for your solution-sharing.


  • 0
    L

    In the nums[cur]==0 case, cur is increased by 1 (cur++);
    But why in the nums[cur]==2 case, cur is not increased by 1?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.