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.
DedupeSorted(ids: list<int>) → list<int>
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public List<int> DedupeSorted(List<int> ids) {
}Worked examples
| Call | Result |
|---|---|
DedupeSorted(new List<int> { 1, 1, 2, 3, 3, 3 }) | new List<int> { 1, 2, 3 } |
DedupeSorted(new List<int> { 1, 2, 3 }) | new List<int> { 1, 2, 3 } |
DedupeSorted(new List<int> { 5, 5, 5, 5 }) | new List<int> { 5 } |
DedupeSorted(new List<int> { }) | new List<int> { } |
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 C#
public List<int> DedupeSorted(List<int> ids) {
var outList = new List<int>();
foreach (var id in ids) {
if (outList.Count == 0 || outList[outList.Count - 1] != id) outList.Add(id);
}
return outList;
}