Anyone with one pass and constant space solution ?


  • 7
    I

    can someone please post the one-pass solution that uses constant space .
    I have been able to do it in two pass only.


  • 187
    X
        public void sortColors(int[] A) {
    	
    	
    	int i=-1, j=-1, k=-1;
    	
    	for(int p = 0; p < A.length; p++)
    	{
    		if(A[p] == 0)
    		{
    			A[++k]=2;
    			A[++j]=1;
    			A[++i]=0;
    		}
    		else if (A[p] == 1)
    		{
    			A[++k]=2;
    			A[++j]=1;
    			
    		}
    		else if (A[p] == 2)
    		{
    			A[++k]=2;
    		}
    	}
        
    }

  • 0
    S

    Hi @xianlei, since your answer has been selected as best answer, I won't hide your post. But discuss do not allow only code post, could you please add words about your algorithm and make key comments in your code? Thanks.


  • 0
    S

    Hi @its_dark, could you please update your post with your two pass code solution and detail how it works? It would make people know more about your question, and will bring them different view of this problem. Thanks.


  • 0
    X

    Ok, I'll do it later. Thanks


  • 0
    A

    It is neat code. I would also appreciate some explanation. Thx


  • 0
    S

    Maintain the starting index of 0s, 1s, and 2s at anytime. (actually, 0s will always start from index 0)
    If next value is 0, right shift 1s and 2s, and put the 0 at proper location.
    For shifting, we don't have to really shift the array, only 3 positions need to be changed.
    Similar for 1 or 2


  • 0
    G

    Using the properties that: 1. we only have 0 1 and 2; 2. 0 follows from first position, 2 ends at last position !


  • 7
    J
    void sortColors(int A[], int n) {
      int i = 0, j = n-1;
      for (int k = 0; k <= j; k++) {
        switch (A[k]) {
          case 0:
            A[k] = 1;
            A[i++] = 0;
            break;
          case 1:
            break;
          case 2:
            A[k--] = A[j];
            A[j--] = 2;
            break;
        }
      }
    }
    

  • 0
    R

    Really smart solution!

    I can describe it in this way:

    • p is the input iterator, reads new values, is as faster than others so no problems of
      reading values already overwritten.
    • i counts the number of 0 found, and a the same time writes zeroes.
    • j counts the number of 0 + 1 found, and at the same time writes 1.
    • k counts the number of 0 + 1 + 2 found and at the same time writes 2.

    Your solution can be improved in this way:

    {
    public void sortColors(int[] A) {

        int i=-1, j=-1;
    
        for(int p = 0; p < A.length; p++) {
    
           int v = A[p];
           A[p] = 2;
    
           if (v == 0) {
    
              A[++j] = 1;
              A[++i] = 0;
           }
           else if (v == 1) {
    
               A[++j] = 1;
           }
        }
    }
    

    }


  • 1
    U

    While xianlei and riccardo's answers are really smart and neat, the running of their codes involves continuous overwriting that compromises the performance. My code is not that beautiful, but it is one-pass with constant space and runs faster. (124 ms vs 180 ms (riccardo's version) by python codes)

    class Solution:
    # @param A a list of integers
    # @return nothing, sort in place
    def sortColors(self, A):
        red, blue = 0, len(A)-1
        i = 0
        while i <= blue:
            if A[i] == 0:
                if i > red:
                    A[red] = 0
                    A[i] = 1
                red += 1
            elif A[i] == 2:
                while blue > i and A[blue] == 2:
                    blue -= 1
                if blue == i:
                    break
                if A[blue] == 0:
                    A[red] = 0
                    if i > red:
                        A[i] = 1
                    red += 1
                else:
                    A[i] = 1
                A[blue] = 2
                blue -= 1
            i += 1

  • 5
    P

    Mine is better and shorter, with a little hacking. Code is in C++

    void sortColors(int A[], int n) {
        int colorIndex[3] = {0};
        for(int i = 0; i < n; i++)
        {
            int color = A[i];
            for (int j = 2; j >= color; j--)
                A[colorIndex[j]++] = j;
        }
    }

  • 0
    M
    public class Solution {
        public void sortColors(int[] A) {
            int i = 0;
            int indexes[] = {0, 0, 0};
            
            while(i < A.length) {
                int num = A[i];
    
                //Correct position
                if(i == indexes[num]) {
                    i++;
                } else {
                    //Exchange
                    A[i] = A[indexes[num]];
                    A[indexes[num]] = num;
                }
                
                //Increments the index
                indexes[num]++;
                
                //Align higher indexes
                for(int o=num+1; o<indexes.length; o++) {
                    if(indexes[o]<indexes[o-1]) indexes[o] = indexes[o-1];    
                }
            }
        }
    }

  • 34
    L
    #include <algorithm> // std::swap
    class Solution {
    public:
        void sortColors(int A[], int n) {
            int j = 0, k = n;
            for(int i=0; i<k; i++)
            {
                if(A[i] == 0)
                    swap(A[j++], A[i]);
                else if(A[i] == 2)
                    swap(A[--k], A[i--]);
            }
        }
    };

  • 0
    J
       void sortColors(int A[], int n) {
            if (n<2) return;
            int numof0 = 0;
            int numof2 = 0;
            int i;
            while ((numof0 < n) && (A[numof0]== 0)) numof0++;
            i = numof0;
            while ((i<n) && (i<(n-numof2))) {
                if ((A[i] ==0) &&  (numof0 != i)) {
                        memmove((void *)&A[1], (void *)A, (i)*sizeof(int));
                        A[0] = 0;
                        numof0++;
                }
                if ((A[i] ==2) && (numof2 < (n-i-1)) ){
                    memmove((void *)&A[i], (void *)&A[i+1], (n-i-1)*sizeof(int));
                    A[n-1] = 2;
                    numof2++;
                    i--;
                }
                i++;
            }
        };
    

    Here is another way for doing it. When you see a '0', insert at the beginning of the array. If you see an '1', leave it. If you see a '2', insert it at the end. Just be careful to "step back" when you insert '2' at the end


  • 0
    K
    This post is deleted!

  • 3
    K

    I scan the whole array one element by one element and swap those elements when some conditions are match. Here is my code. I found it more readable. Comments are welcome!

     class Solution {
        public:
            void sortColors(int A[], int n) {
                int left = 0;
                int right = n - 1;
                int current = 0;
                
                while (current <= right) {
                    if (A[current] == 0) {
                        swap(A[current], A[left++]);
                    } else if (A[current] == 1) {
                        current++;
                    } else {
                        swap(A[current], A[right--]);
                    }
                    current = max(current, left);
                }
                
                return;
            }
        };

  • 2
    R

    Modified version from the top one.

    public class Solution {
    public void sortColors(int[] A) {
        int red,white,blue;
        red=0;white=0;blue=0;
        for(int i=0;i<A.length;i++){
            int current=A[i];
            if (current<=2)
                A[blue++]=2;
            if (current<=1)
                A[white++]=1;
            if (current<=0)
                A[red++]=0;
        }
    }
    

    }


  • 0
    Y

    Hello, this is my O(n) solution,constant space. the idea is similar to partition technique in quick sort.
    index p1 to denote the last position of 0
    p2 to denote last position of 1(if there is).

    public void sortColors(int[] A) {
        int n=A.length;
        int p1=-1;
        int p2=-1;
        for(int i=0;i<n;i++){
            if(A[i]==0){
                p1++;
                swap(A,p1,i);
                if(p2!=-1){
                    p2++;
                    swap(A,p2,i);
                }
            }
            else if(A[i]==1){
                if(p2==-1)
                    p2=p1;
                p2++;
                swap(A,p2,i);
            }
        }
    }
    
    public void swap(int[] A,int i,int j){
        int temp=0;
        temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
    

  • 0
    W
    void sortColors(int A[], int n) {
            int mark_0 = 0;
            int mark_1 = 0;
            int mark_2 = 0;
            for(int i=0;i<n;i++){
                if(A[i]==0){
                    A[mark_0] = 0;
                    if(mark_1!=mark_0)
                        A[mark_1] = 1;
                    if(mark_2!=mark_1)
                        A[mark_2] = 2;
                    mark_0++;
                    mark_1++;
                    mark_2++;
                }
                else if(A[i]==1){
                    A[mark_1] = 1;
                    if(mark_2!=mark_1)
                        A[mark_2] = 2;
                    mark_1++;
                    mark_2++;
                }
                else if(A[i]==2){
                    A[mark_2] = 2;
                    mark_2++;
                }
            }
        }

Log in to reply
 

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