cassidoo_problem_08162020.py

# This week’s question:
# Given an array of random integers, move all the zeros in the array to the end of the array. Try to keep this in O(n) time (or better)!

# Example:
# $ moveZeros([1, 2, 0, 1, 0, 0, 3, 6])
# $ [1, 2, 1, 3, 6, 0, 0, 0]

def _get_end_pointer(l, end_pointer=-1):
    while l[end_pointer] == 0 and -end_pointer < len(l):
        end_pointer -= 1
    return end_pointer

def _swap(l, start_pointer, end_pointer):
    l[start_pointer], l[end_pointer] = l[end_pointer], l[start_pointer]

def move_zeros(l):
    '''
    Move through the array, swapping every zero element with the last nonzero element in the list.
    Once the start pointer is equal to the end pointer,
    all zeros will be to the left of the end pointer.
    Note this solution
    '''
    # End pointer always points to the last nonzero element in the list
    end_pointer = _get_end_pointer(l)

    start_pointer = 0
    while start_pointer <= (len(l) + end_pointer):
        if l[start_pointer] == 0:
            _swap(l, start_pointer, end_pointer)
            end_pointer = _get_end_pointer(l, end_pointer)
        start_pointer += 1

    return l

def check(l):
    first_zero = l.index(0) if 0 in l else -1
    assert sum(l[:first_zero]) == sum(l), "Check failed for {}".format(l)

if __name__ == "__main__":
    check(move_zeros([1, 2, 0, 1, 0, 0, 3, 6]))
    check(move_zeros([0,0,0,0]))
    check(move_zeros([0,0,0,0,4,3,2,1,0]))