Collapse repeated heartbeat quotes

Question

A quote feed re-publishes the current top-of-book on a heartbeat, so when nothing changes you receive the identical message many times back to back. You only want to forward a message when it differs from the one immediately preceding it. Note this is not global dedup: a value that returns later, after something else came between, is a real change and must pass through.

stream = ["A", "A", "B", "B", "B", "A", "C", "C"]
-> ["A", "B", "A", "C"]

Remove only consecutive duplicates, preserving order, in $O(1)$ extra space.

Accepted Answer

Because only adjacent repeats matter, you never need a set of everything seen, just the previous value. Emit the current message whenever it differs from the last one you emitted. Tracing the example: A starts the output; the second A matches out[-1] and is dropped; B differs and passes; the two extra Bs drop; A differs from B so it passes again (this is the return that global dedup would wrongly kill); C passes; the trailing C drops. Result ["A","B","A","C"]. Time O(n); space O(1) beyond the output, since we only ever look at out[-1]. If you must compress a list in place, keep a write index …

Collapse repeated heartbeat quotes

Your answer

More Coding questions