My C++ solution with one pass and O(n) time and O(n) space


  • 21
    A
    class Solution {
    public:
    //use counting sort
    void sortColors(int A[], int n) {
    int red = -1, white = -1, blue = -1;
    
    for(int i = 0; i < n; i++){
        if(A[i] == 0){   
            A[++blue] = 2;
            A[++white] = 1;
            A[++red] = 0;
        }
        else if(A[i] == 1){
            A[++blue] = 2;
            A[++white] = 1;
        }
        else if(A[i] == 2)   
            A[++blue] = 2;
    }
    }
    };
    

    the clever thing is that use three variable to store the three colors' index position.
    When you face A[i] == 0, all the variables add 1 because 0 is former.
    Do the same thing to other 2 situation.

    Ex:
    If you just face 2, just need to assign 2 to the A[++blue], and "++blue" will increase "blue" with 1.
    Next if you face 0, you will increase 3 variable and assign the number to A!

    It will make sure you always get the right sorted array when you run the for loop.


  • 1
    L

    Your answer is brilliant. We have the same idea, but mine is less verbose and more generic.

    class Solution {
    public:
        void sortColors(int A[], int n) {
            int f[3]={0}; // store the frequencies
            int i,j,k;
            for(i=0;i<n;i++){
                int cur=A[i];
                f[cur]++;
                int prev=cur;
                // basically this loop will insert the new element, cur.
                // same principle as the answer above, but condensed into a loop.
                for(k=j=0;j<=2;j++){
                    k+=f[j]; // k is cumulative freq.
                    if(j>=cur&&f[j]){  
                        // replace the element that is occupying the new element (cur)'s 
                        //rightful place, and store the old element in prev
                        swap(A[k-1],prev);
                    }
                }
            }
        }
    };

  • 0
    O
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    W

    there are 4 memory accesses (worst case) for each iteration. Maybe worse than a simple two passes solution.


  • 0
    K

    you can do ++blue, ++white, ++red without modifying A[] I think. And the space is O(1)?


  • 0
    L

    Could you change your title to O(1) space? Now it is O(n) and misleading.


  • 0
    Y

    your solution is O(1) space, not O(n)


Log in to reply
 

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