O(n) 4ms C++ with comments


  • 0
    C
    class Solution {
        const int RED= 0, WHITE= 1, BLUE= 2;
    public:
        void sortColors(vector<int>& nums) {
            // Setup pointers : rp -Red Pointer, bp- Blue Pointer
            // Scan array starting with pos=0
            int rp = 0, bp= nums.size() -1, pos= 0;
            while (pos <= bp) { // scan till sorted BLUE side is met
              if (nums[pos]==RED && pos!=rp) { // RED : move to left-side
                    swap(nums[pos], nums[rp]); 
                    rp++;
              }
              else if (nums[pos]==BLUE) { // BLUE : move to right-side
                    swap(nums[pos], nums[bp]); 
                    --bp;
              }
              else { // WHITE : keep in place, check the next
                    pos++;
              }
            }
        }
    };

Log in to reply
 

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