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

Answer 2

You need two indices, one for reading and of writing:

def remove_element(value, array):
    reading_idx = writing_idx = 0
    while reading_idx < len(array):
        if array[reading_idx] != value:
            array[writing_idx] = array[reading_idx]
            writing_idx += 1
        reading_idx += 1
    while writing_idx < len(array):
        array[writing_idx] = None
        writing_idx += 1

Answer 3

This might be cheating, but...

def remove(value, array):
    try:
        while True:
            del(array[array.index(value)])
            array.append(None)
    except ValueError:
        pass

    return array

Answer 4

Code:

def removeSingleElement(value, array):
    """
    Remove value from the input array.
    Input parameters:
        value: Remove Value.
        array: Input array.
    Output parameters:
        return array.
    """
    #- Length of array.
    array_length = len(array)
    i = array_length - 1

    #- Iterate Array from higher index to Lower index.
    while i > -1:
        #- Check Current item value with remove value.
        if array[i] == value:
            #- Remove Value from the input list.
            array.pop(i)
            #- Append None value to input list.
            array.append(None)
        #- Decrement index value by 1
        i -= 1

    return array


remove_item = 'x'
input_array = ['x', 1, 2, 3, 'x', 4, 5, 'x']

output_array = removeSingleElement(remove_item, input_array)

print "Output:", output_array

Output:

vivek@vivek:~/Desktop/stackoverflow$ python remove_item.py 
Output: [1, 2, 3, 4, 5, None, None, None]