2

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 ;)

Improve this question
6
  • Lol @Daniel I wish I were still in school :) No this came up during an interview and I'm trying to figure out what the trick was. Commented Jun 21, 2015 at 16:05
  • not getting.. means input is [1,2,3,'x',4,5] and output will be [1,2,3,4,5, None] .. more input is [1,2,3,'x',4,5 'x'] and output will be [1,2,3,4,5] after remove x value from the input list. Commented Jun 21, 2015 at 16:11
  • 1
    You don't need to shift the elements before the frst x. You need to shift elements between the first x and the second x one place to the left. You need to shift elements between the second x and the third x two places to the left. You need to shift elements between the third x and the fourth x three places to the left. You... Commented Jun 21, 2015 at 16:12
  • @n.m. : ha! thanks, that is what I was looking for. So simple once you know the solution :) Commented Jun 21, 2015 at 16:19
  • "No extra memory/data structures are allowed" should be "only a constant amount of extra memory is allowed" for the task to make any sense Commented Jun 21, 2015 at 19:08

4 Answers 4

Reset to default
2

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
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Nice catch the repeated values bug. I like this solution, thanks! :)
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
Improve this answer

5 Comments

You are iterating the list twice (at least partially).
What does the second while loop do? It iterates through the list, right?
@thefourtheye: he's not exactly iterating twice, he is traversing the array once with two pointers. The second while loop just sets the leftovers (if any) to None.
@laurids It means that iterating the list twice.
@thefourtheye I see what you mean but I don't think there's a way to do it otherwise (without using try/except as in the accepted answer). It is still pretty neat code, I'm grateful to Daniel for the contribution.
0

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]
Improve this answer

1 Comment

The whole point of the question was to do it without modifying the array - pheraphs I wasn't clear enough about it. Check out Eric's and Daniel's answers ;)
0

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
Improve this answer

2 Comments

this will work for ['x', 'x', 1, 2, 'x', 'x'] input ?
You are right, it doesn't, but updated one does. Though it doesn't answer the question as OP is looking for generic algorithm

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.