Remove values from an array in-place without using extra memory

Question

I want to remove value x from an array and I have the following constraints:

1. I can only traverse the array once
2. No extra memory/data structures are allowed

so that

a = [1, 2, 'x', 3, 4, 5]

becomes

[1, 2, 3, 4, 5, None]

The case with only one x is trivial, I just shift everything one position left:

def removeSingleElement(value, array):
    i = 0
    while i < len(array)-1:
        if array[i] == value:
            for val in array[i:-1]:
                array[i] = array[i+1]
                i += 1 
        else:
            i += 1

    array[-1] = None
    return array

but how do I cope with an array with repeated values?

a = [1, 'x', 2, 3, 'x', 4]

should become

a = [1, 2, 3, 4, None, None]

(the idea is that I can't resize the array so I want to shift everything on the left and fill the rest with Nulls values).

Disclaimer: this is not a Python question, I'm looking for the general algorithm and it just happens that I find Python convenient to express the idea ;)

Answer 1

Assuming that you are allowed to know the length of the array in advance and store a counter the following works:

def remove_element(value,array):
    shift = 0
    for index in xrange(len(array)):
        try:
            array[index] = array[index + shift]
            while array[index] == value:
                shift += 1
                array[index] = array[index + shift]
        except IndexError:
            array[index] = None