Collapse repeats in a sorted feed
A sorted export repeats an id whenever a row was touched twice. The importer wants each id once, still in order.
- The input arrives sorted ascending, so equal values are always adjacent.
- Each distinct value survives once, in the order it first appeared.
- An empty feed comes back empty.
dedupe_sorted(ids: list<int>) → list<int>
Where you start
def dedupe_sorted(ids: list[int]) -> list[int]:
Worked examples
| Call | Result |
|---|---|
dedupe_sorted([1, 1, 2, 3, 3, 3]) | [1, 2, 3] |
dedupe_sorted([1, 2, 3]) | [1, 2, 3] |
dedupe_sorted([5, 5, 5, 5]) | [5] |
dedupe_sorted([]) | [] |
Hint
Because it is sorted you only ever need to compare against the value you kept last. Walk forward and keep a value only when it differs from that one.
Reference solution in Python
def dedupe_sorted(ids: list[int]) -> list[int]:
out = []
for value in ids:
if not out or out[-1] != value:
out.append(value)
return out