My python solution with one Pass, constant space and O(n) time, any improvement?


  • 0
    W
    def sortColors(self, A):
        i = 0
        j = len(A) - 1
        idx = 1
        while True:
            if A[i] > A[j]:
                A[i],A[j] = A[j],A[i]
            while A[i] == 0 and i < j:
                i += 1
                idx = i + 1 
            while A[j] == 2 and j > i:
                j -= 1
            if i >= j or idx > j:break
            if A[i] == 1 and A[j] == 1:
                if A[idx] == 0:
                    A[idx],A[i] = A[i],A[idx]
                    i += 1
                elif A[idx] == 2:
                    A[idx],A[j] = A[j],A[idx]
                    j -= 1
                idx += 1

Log in to reply
 

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