Squeezing out duplicates in place

You have a sorted list where some values repeat: [1, 1, 2, 3, 3]. You want each value once: [1, 2, 3]. Same order, no repeats.

The simplest way is to make a new list and copy the values you keep into it. That works, but it takes twice the memory: for a while both lists sit in memory at once. Sometimes the list is huge. Sometimes it is a buffer (a stretch of memory that holds data) that the program reuses thousands of times a second. Then the second copy may cost more memory than you have.

The sorted order helps. In a sorted list, equal values always stand next to each other. So you can rewrite the list you already have and spend almost no extra memory.

In a sorted list, repeats stand next to each other. You want one copy of each value, written into the same list.

Walk the list from left to right and look at every number. A number is new when it differs from the number before it. Copy each new number to the front of the list, into the first free place. Skip each repeat.

On [1, 1, 2, 3, 3] it goes like this. Keep the first 1. Skip the second 1. Write 2 into the 2nd place and 3 into the 3rd. Skip the last 3. The list now starts with 1, 2, 3, and you never needed a second list.

Take two markers. Both move the same way, at different speeds. The fast read marker (read) looks at every element. The slow write marker (write) remembers where the next kept value goes.

The list is sorted, so a value is new exactly when it differs from its left neighbour. So read compares the current value with the element before it. If the value is new, copy it into the write cell and move write one step forward. If it is a repeat, skip it: only read moves on.

In lesson 19 the two markers closed in from opposite ends. Here both move from left to right. The slow marker shows where to write, and it does not limit the search.

Trace it on [1, 1, 2, 3, 3]. Start with write = 1: the first element always stays.

• read=1: 1 == 1, a repeat, skip it.
• read=2: 2 != 1, write 2 into cell 1, and write becomes 2. The array is now [1, 2, 2, 3, 3].
• read=3: 3 != 2, write 3 into cell 2, and write becomes 3. The array is now [1, 2, 3, 3, 3].
• read=4: 3 == 3, a repeat, skip it.

The first 3 cells are [1, 2, 3], and the new length is 3. Cells 3 and 4 still hold old values. Nobody checks them.

Time is O(n): read visits each element once, and write only moves forward. Memory is O(1): the list is rewritten inside itself, with no extra structure.

You could put every kept value into a hash set (the Set from the lesson on sets) and build the list from it. That is also O(n) time, but it takes O(n) memory. On sorted input that memory is wasted: the comparison with the previous element tells you everything the set would.

Analytics systems get events from at-least-once delivery. That kind of delivery guarantees an event arrives, but it sometimes sends the same event twice. Before passing a sorted buffer of events on, the system removes the repeats in place. Databases throw away rows marked for deletion during compaction (a pass that rewrites stored data more tightly). The uniq command removes repeats from a sorted stream of lines. Wherever a sorted buffer has to shrink without a second buffer, a write pointer does the job. Often this is on a hot path, that is, code that runs very often.