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.
del self.items[x]
?.pop
and.remove
, i.e., it will be O(N^2) overall to remove the elements from the list.