My O(n), constant space solution


  • -3
    M
    class Solution {
    public:
        void sortColors(int A[], int n) {
            int count0=0, count1=0, count2=0;
            
            for(int i=0; i<n; i++)   //count the occurance of 0,1,2
            {
                if(A[i]==0)
                count0++;
                else if(A[i]==1)
                count1++;
                else count2++;
            }
    
            int i0=0, i1=0, i2=0;
            
            //put the respective occurance of each number
            while(i0<count0)  
            A[i0++]=0;
                
            while(i1<count1)
            A[i0+i1++]=1; 
                
            while(i2<count2)
            A[i0+i1+i2++]=2; 
            
            
        }
    };

  • 0
    W
    This post is deleted!

  • 0
    R

    it's very tricky, but I don't think it is the expected answer of the asker


  • 0
    L

    your is not one-pass


Log in to reply
 

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