O(n) complexity algorithm to remove instances of value from unsorted list without remove() method

Question

I have a homework question to write a function which is part of a class bagOfWords to remove instances of a value from an unsorted list. The list operations we can use don't include remove(). We need to have only O(n) complexity and the naive algorithm doesn't perform that well.

I tried a naive algorithm. This is too complex an algorithm. It uses list.pop(index) which of itself has O(n) complexity and it has two loops. Since we are not allowed to use list.remove() and because a list comprehension would have the same complexity but in a more succinct syntax, I'm trying to find a better implementation.

I thought maybe the solution was a quicksort algorithm because I might be able to do this with O(n) complexity if I first sort the list. But how would I then remove this item without the complexity of pop(index)? Now I'm wondering if searching for the pattern via a KMP algorithm would be the solution, or hashing.

 def remove(self, item):
        """Remove all copies of item from the bag. 
        Do nothing if the item doesn't occur in the bag.
        """
        index = 0
        while index < len(self.items):
            if self.items[index] == item:
                self.items.pop(index)
            else:
                index += 1

The complexity is quadratic. However, I want a complexity that is O(n)

Edit: to clarify, we are actually constrained to modifying an existing list.

Answer 1

Edit: The simplest (and arguably just "correct") way to do this is to use a list comprehension:

self.items = [x for x in self.items if x != item]

It's O(n), and it's faster than the below options. It's also by far the most "pythonic".

---

However, it does create a new copy of the list. If you are actually constrained to modifying an existing list, here's my original answer:

Here's an "in-place" O(n) algorithm that uses two pointers to collapse the list down, removing the unwanted elements:

ixDst = 0
for ixSrc in range(0, len(items)):
  if items[ixSrc] != item:
    items[ixDst] = items[ixSrc]
    ixDst += 1
del items[ixDst:]

(See it run here)

The only questionable part is resizing the list down with del. I believe that's in-place and "should" be O(1), since the slice we're removing is at the end of the list.

Also, a more pythonic in-place answer (and a bit faster) was suggested by @chepner in the comments:

self.items[:] = (x for x in self.items if x != item)

Thanks @juanpa.arrivillaga and @chepner for the discussion.