My c++ solution 4ms, 7 line of code, constant space


  • 3
    Y

    loop invariant is in comment

    
    void sortColors(vector<int>& nums) {
        int sz = nums.size();
        int curr=0, l=-1,r=sz;
        while(curr<r){
            // 0: <=l
            // 1: l< <curr
            // 2: r<=
            // unsort: curr<= <r
            if(nums[curr]==0) swap(nums[++l], nums[curr++]);        
            else if(nums[curr] == 1) curr++;
            else swap(nums[curr], nums[--r]);
        }
    }

Log in to reply
 

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