7-liner O(N) without swapping duplicates


  • 0

    NOTE: this solution does not swap duplicates values in the array, which is efficient.

       void sortColors(vector<int>& a) {
            // i0, i1, i2: next position to set 0, 1, 2
            auto i0 = a.begin(), i1 = i0, i2 = a.end()-1;
            while (i1 <= i2)
                if (*i0 == 0) i1 = ++i0;
                else if (*i2 == 2) --i2;
                else if (*i1 == 0) swap(*i1, *i0++);
                else if (*i1 == 2) swap(*i1, *i2--);
                else ++i1;
       }
    

Log in to reply
 

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