Lesson 04: Stop Deleting Array Elements the Hard Way: The O(n) Trick Every DSA Interviewer Expects You to Know

Master the Two-Pointer Technique for Removing Elements In-Place — Learn How Read and Write Pointers Help You Remove Unwanted Products from Varastra's Catalog in O(n) Time and O(1) Extra Space.

The interview insight: You don't always need to delete an element. Sometimes, the smarter solution is to overwrite the elements you want to keep and ignore the rest.

A loop that removes items while it walks the same list can skip some of them. The test passes with one item. It fails with two in a row. Here is why, and a clean fix with two indexes.

The problem at Varastra

Varastra is an online store for Indian ethnic wear. It keeps a list of parcel IDs for each courier pickup. When a customer cancels an order, the parcel is marked "X". Before the courier arrives, every "X" must go.

Dev, a developer, writes four lines of code. He tests them on a list with one cancelled parcel in the middle. The test passes. He merges the code.

The next morning, the warehouse calls. A cancelled parcel went out with the courier. The customer got a saree she had cancelled. Varastra paid the courier twice, once to deliver and once to bring it back. (This story is made up.)

Sam, a senior engineer, types a new test with three items: ["X", "X", "A"]. The expected result is ["A"]. The real result is ["X", "A"]. One cancelled parcel is still there.

Why the loop skips an item

Here is Dev's code.

def remove_all_bad(a, value):
    for x in a:
        if x == value:
            a.remove(x)

Pause and predict

Before you read on: what does remove_all_bad return for ["X", "X", "X", "A"]?

Answer: ['X', 'A']. One X is left. After each removal, the next X slides into the spot the loop just left.

Tara, a new intern, traces it on paper with ["X", "X", "A"].

1. The loop looks at index 0. It sees "X" and removes it.
2. The list is now ["X", "A"]. The second "X" slides into index 0.
3. The loop moves on to index 1. It sees "A".
4. It never looks at index 0 again.

The loop moved forward. The list moved backward. They crossed, and one item was never checked.

t = ["X", "X", "A"]
remove_all_bad(t, "X")
print(t)   # ['X', 'A']

Dev's test had only one "X". One cancelled item cannot trigger this bug. So always test with two equal items in a row.

The slow fix

The simple fix is to call remove again and again until nothing is left.

def remove_all_slow(a, value):
    while value in a:
        a.remove(value)      # every call shifts the rest of the list

This is correct. But every removal shifts all the items after it one place to the left. (The previous article explains shifting.) Each value in a also scans the list from the start.

Here is how long cleaning takes when 40% of the items are cancelled.

import time, random

def make_list(n):
    return ["X" if random.random() < 0.4 else f"P{i}" for i in range(n)]

for n in (10_000, 20_000, 40_000, 80_000):
    data = make_list(n)
    start = time.perf_counter()
    remove_all_slow(data[:], "X")
    slow = time.perf_counter() - start
    start = time.perf_counter()
    remove_all_in_place(data[:], "X")     # the fix below
    fast = time.perf_counter() - start
    print(n, round(slow, 4), round(fast, 4))

From 20,000 items on, the first column grows about 4.4 times each time n doubles. That is the O(n²) shape. A pickup list of 200,000 parcels would take about 80 seconds this way. That figure is an estimate from the 80,000 row. It was not timed.

These numbers were measured on one machine. They will differ on yours.

The fix: a read index and a write index

The fix uses two indexes that walk the same list.

• The read index looks at every item once.
• The write index marks where the next kept item goes.

The rules are short:

1. If the read index finds an item to keep, copy it to the write index. Then move the write index forward by one.
2. If it finds a cancelled item, skip it. Do nothing.
3. At the end, cut off everything after the write index.

def remove_all_in_place(a, value):
    write = 0
    for read in range(len(a)):
        if a[read] != value:
            a[write] = a[read]
            write += 1
    del a[write:]
    return len(a)

The diagram traces ["X", "X", "A", "B"]:

1. Read 0 is "X". Skip it. Write stays at 0.
2. Read 1 is "X". Skip it. Write stays at 0.
3. Read 2 is "A". Copy it to slot 0. Write moves to 1.
4. Read 3 is "B". Copy it to slot 1. Write moves to 2.
5. Cut the list after slot 1.

The result is ["A", "B"].

Each item is read once and written at most once. No item shifts again and again. The cost is O(n) time and O(1) extra space. The same list is changed, so every part of your program that holds this list sees the clean result.

Try it

Run both versions on ["A", "X", "B", "X", "X"] and compare. What do you expect?

remove_all_bad gives ['A', 'B', 'X'], so one X survives. remove_all_in_place gives ['A', 'B'] and returns 2.

Test it properly

A fix is only as good as its tests. Tara writes four, and one has two cancelled parcels in a row.

def test_remove_all():
    cases = [
        ([], []),
        (["A"], ["A"]),
        (["X"], []),
        (["X", "X", "A"], ["A"]),
        (["X", "X", "A", "B"], ["A", "B"]),
        (["A", "X", "B", "X", "X"], ["A", "B"]),
    ]
    for data, expected in cases:
        a = data[:]
        count = remove_all_in_place(a, "X")
        assert a == expected
        assert count == len(expected)

test_remove_all()
print("all tests pass")

Tara also compares it with the slow version on random lists. If the fast version and the slow version agree on 500 lists, a bug is unlikely.

The shorter way, and its catch

Python has a short way to clean a list.

parcels = [p for p in parcels if p != "X"]

It is fast and clean, and it is often the best answer. But it has a catch. It builds a new list and points the name parcels at it. Any other code that still holds the old list will still see the cancelled parcels. It also uses O(n) extra space.

So the wording of the problem decides:

• If the problem says "in place" or "O(1) extra space", use the read and write index.
• If it does not, and nobody else holds the list, the new list is fine.

How to spot this pattern

1. The problem says "remove", "filter" or "delete" items from a list.
2. The problem says "in place" or "without extra space."
3. The order of the kept items must stay the same.

When you see these, think about two indexes. One reads. One writes. Say it out loud:

"I will use a read index and a write index. Each item is read once, so the time is O(n), and the extra space is O(1)."

Takeaway: Never remove items from a list while you loop over it. Use a read index and a write index, and always test with two equal items in a row.