[Accepted] My working constant space solution


  • 0
    L

    This is my constant space solution. It basically tracks the last 0 and first 2 in the partially sorted array. During the pass, for example, we are on the fifth element.
    0 0 0 1 ? x x x x 2 2
    If it's 0, we will swap it with the first nonzero element; if it's 1, keep it that way; if it's 2, they swap with the third last element.

    Let me know if there is more room for improvement!

       class Solution {
            public:
              
              void swap(int A[], int i, int j)
              {
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
              }
              
              void sortColors(int A[], int n)
              {
                int ind0(0), ind2(n-1);
                
                int i=0;
                while (i<n)
                {
                  if (A[i]==0)
                  {
                    if (i==0 || A[i-1]==0)
                    {
                      ++i;
                      ind0 = i;
                    }
                    else if (A[i-1]!=0)
                    {
                      swap(A,i,ind0);
                      ind0++;
                    }
                  }
                  else if (A[i]==1)
                  {
                    ++i;
                  }
                  else if (A[i]==2)
                  {
                    if (i < ind2)
                    {
                      if (A[ind2] != 2)
                        swap(A,i,ind2);
                      --ind2;
                    }
                    else
                    {
                      ++i;
                    }
                  }
                }
              }
            };

Log in to reply
 

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