Deduplicate While Preserving Order

Map by ID (first wins)

TimeO(n)SpaceO(k), k = unique idsGood solution

Single pass over the input. Each id is looked up and at most once inserted; Map operations are O(1) average. Output size is O(k). Optimal for this problem.

Code

1type Item = {
2    id: string
3    title: string
4    timestamp: number
5}
6
7function dedupe(items: Item[]): Item[] {
8    const m = new Map<string, Item>();
9    for (const item of items) {
10        if (m.has(item.id)) {
11            continue;
12        }
13        m.set(item.id, item); 
14    }
15    return Array.from(m.values());
16}
17
18const items: Item[] = [
19    { id: "a", title: "Post A", timestamp: 1 },
20    { id: "b", title: "Post B", timestamp: 2 },
21    { id: "a", title: "Post A (duplicate)", timestamp: 3 },
22    { id: "c", title: "Post C", timestamp: 4 },
23    { id: "b", title: "Post B (duplicate)", timestamp: 5 }
24  ]
25
26const deduplicatedItems = dedupe(items);
27console.log(deduplicatedItems);

Animation

Input

aPost At=1

bPost Bt=2

aPost A (duplicate)t=3

cPost Ct=4

bPost B (duplicate)t=5

Output

(first occurrence of each id)

Speed: