Remove repeated readings from a sorted log in place

Two pointers Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
log = [1, 1, 2, 2, 2, 5]
w = 1
for r in range(1, len(log)):
    if log[r] != log[w - 1]:
        log[w] = log[r]
        w += 1
print(log[:w], w)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [1, 2, 5] 3

Right: three distinct readings are packed at the front.

The tail beyond w still holds old values; only the first w slots are the answer, which is why the real function trims it.

Why not the others?
  • B [1, 2, 2, 5] 4. Each repeat of 2 equals the last kept value and is skipped.
  • C [1, 1, 2, 2, 2, 5] 6. The write pointer only advances on a new value.

30-second answer

Use a write pointer that marks the end of the kept part. Scan with a read pointer; whenever the reading differs from the last kept one, write it and advance. Sorted input guarantees repeats sit next to each other, so one pass is enough: O(n) time, O(1) extra space.

Practise saying it · 30 s. No recording, just a timer

Explain in-place deduplication of a sorted list.

Say your answer out loud, then check which of these points you covered:

  • Write pointer
  • Compare with last kept value
  • O(n) time, O(1) space

Deep dive

Comparing with the last kept value (not the previous raw value) is what makes the rule simple and correct.

del log[write:] trims the tail in O(n - write) once at the end.

list(dict.fromkeys(log)) removes repeats and keeps order for any input, but builds new objects.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def dedupe(log: list[int]) -> list[int]:
    write = 0
    for read in range(len(log)):
        if write == 0 or log[read] != log[write - 1]:
            log[write] = log[read]
            write += 1
    del log[write:]
    return log

Common mistakes

  • Deleting items while iterating forward over the same list, which skips elements.
  • Assuming the input is sorted when it is not; then repeats are not adjacent.

Senior take & follow-ups

Mention why sortedness matters: it turns 'have I seen this?' into 'is this the same as the last kept value?'.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if each value may stay at most twice?

    Show hint

    Compare with the value two places behind the write pointer.

  2. What if the log is unsorted?

    Show hint

    Keep a set of seen values; O(n) time but O(n) space.

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.