Python solution with one pass and constant space


  • 0
    S
    class Solution:
        # @param A a list of integers
        # @return nothing, sort in place
        def sortColors(self, A):
            last_r, last_w = -1, -1
            for i in xrange(len(A)):
                if A[i] == 0:
                    if i > last_r + 1:
                        A[i], A[last_r + 1] = A[last_r + 1], A[i]
                    last_r += 1
                if A[i] == 1:
                    if last_w < last_r:
                        last_w = last_r
                    if i > last_w + 1:
                        A[i], A[last_w + 1] = A[last_w + 1], A[i]
                    last_w += 1

Log in to reply
 

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