That is my solution. constant space and one pass


  • 0
    A
    class Solution {
    public:
        void swap( int A[], int a, int b )
        {
            int temp = A[ a ];
            A[ a ] = A[ b ];
            A[ b ] = temp;
        }
        void sortColors(int A[], int n) {
            int st = 0, ed = n - 1;
            int temp = 0;
            for ( int i = 0; i <= ed; i++ )
            {
                if ( A[ i ] == 0 )
                {
                    swap( A, st++, i );
                }
                if ( A[ i ] == 2 )
                {
                    while ( ed >= 0 && A[ ed ] == 2 )
                    ed--;
                    if ( ed < i )
                    break;
                    swap( A, ed--, i );
                    if ( A[ i ] == 0 )
                    swap( A, st++, i );
                }
            }
        }
    };

Log in to reply
 

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