Single Traversal O(n) Time and O(1) space - Python Solution

class Solution:
    # @param A : list of integers
    # @return a list of integers
    def solve(self, A):
        l = 0
        r = len(A) - 1

        while l<r:
            # if A[l] points to '1' and A[r] points to '0', then swap, increment l and decrement r
            if A[l] > A[r]:
                A[l],A[r] = A[r],A[l]
                l+=1
                r-=1
            # if A[r] is already '1', just decrement r
            elif A[r] == 1:
                r-=1
            # in this state, A[0] should definitely be '0', so just increment l
            else:
                l+=1
            
        return A
Click here to start solving coding interview questions