How can I remove all elements matching a predicate from a list IN-PLACE?

T = TypeVar("T")def remove_if(a: list[T], predicate: Callable[[T], bool]):# TODO: Fill this in.# Test:
a = [1, 2, 3, 4, 5]
remove_if(a, lambda x: x % 2 == 0)
assert(a == [1, 3, 5])

The answer should be O(N); not O(N^2).

Here is a similar question but it does not require IN-PLACE removal: Removing an element from a list based on a predicate

In Rust this is Vec::retain(). In C++ it is std::remove_if() (plus erase()).

Is there an equivalent in Python?

This does the trick using the standard algorithm. It does unnecessarily copy elements to themselves before the first failure of the predicate, so you may want to add a find() at the start of the loop (see the "Possible Implementation" for C++'s std::remove_if()). It should still be pretty fast though and that doesn't affect the complexity which is O(N).

from typing import Callable, TypeVarT = TypeVar("T")def remove_if(lst: list[T], predicate: Callable[[T], bool]):i = 0for element in lst:if not predicate(element):lst[i] = elementi += 1del lst[i:]

Edit: @mozway's answer is a lot simpler and probably O(N) too. You would need to benchmark to see which is actually faster because his probably isn't in-place in memory terms (though it is in-place in logical terms).

a[:] = [x for x in a if x%2==0]