Share my at most two-pass constant space 10-line solution


  • 451
    Y

    The idea is to sweep all 0s to the left and all 2s to the right, then all 1s are left in the middle.

    It is hard to define what is a "one-pass" solution but this algorithm is bounded by O(2n), meaning that at most each element will be seen and operated twice (in the case of all 0s). You may be able to write an algorithm which goes through the list only once, but each step requires multiple operations, leading the total operations larger than O(2n).

        class Solution {
        public:
            void sortColors(int A[], int n) {
                int second=n-1, zero=0;
                for (int i=0; i<=second; i++) {
                    while (A[i]==2 && i<second) swap(A[i], A[second--]);
                    while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
                }
            }
        };

  • 0
    X

    Brilliant solution! I gave you a vote up. :)


  • 77
    J

    Diao Bao Le!


  • 6
    M

    This is a nice solution, but I mean, if the input set is like 0000000020, literally i + zero is greater than one iteration. But, anyway, a really good method to learn. Also, I think the definition of one pass or two pass is not really clear.


  • 93
    D

    My java version is more readable, the basic idea is to use two pointer low and high and an iterator i

    every elem left low pointer is 0, elem right high pointer is 2

       public void sortColors(int[] A) {
           if(A==null || A.length<2) return;
           int low = 0; 
           int high = A.length-1;
           for(int i = low; i<=high;) {
               if(A[i]==0) {
                  // swap A[i] and A[low] and i,low both ++
                  int temp = A[i];
                  A[i] = A[low];
                  A[low]=temp;
                  i++;low++;
               }else if(A[i]==2) {
                   //swap A[i] and A[high] and high--;
                  int temp = A[i];
                  A[i] = A[high];
                  A[high]=temp;
                  high--;
               }else {
                   i++;
               }
           }
       }

  • 30
    Q
    class Solution {
    public:
        void sortColors(int A[], int n) {
            int i = 0, j = n-1;
            for(int k=0; k<=j; )
            {
            	if(A[k]==0)  swap(A[i++], A[k++]);
            	else if(A[k]==2)  swap(A[j--], A[k]);
            	else k++;
            }        
        }
    };
    

    With hint from your code.
    Also two pointers.


  • 1
    T

    my solution is almost same as yours!


  • 0
    M
    This post is deleted!

  • 1

    Damn clever idea!


  • 0
    S
    This post is deleted!

  • 5
    N

    There is a question. why change the order as
    while (A[i]==0 && i>zero) swap(A[i], A[zero++]);
    while (A[i]==2 && i<second) swap(A[i], A[second--]);
    Then result is wrong?


  • 0

    Hi, NickYY. The reason will become obvious if you try some examples :-)


  • 0
    L

    不, 是你的益达!!!!!!!!!!!!!


  • 0
    R

    ............niu bi


  • 0
    P

    concise and readable!


  • 0
    A

    what is the time complexity?


  • 0
    R

    +1, could someone explain what is the time complexity of this solution? Thanks!


  • -1
    W

    Its urs YIDA


  • 0
    G

    Genius!!!! hui wan!!!!


  • 0
    D

    ..........................Indeed!


Log in to reply
 

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