Grouping and Deduplicating with Maps

Two of the most common "reshape this data" tasks in frontend code — grouping a flat list by some field, and removing duplicates by a chosen key — are both one-pass, map-based algorithms once you see them that way. Both replace "for each item, search everything else" with "for each item, do O(1) work using a map," the same idea running through this entire part of the course.

Grouping: one map, one pass

function groupBy(items, keyFn) {
  const groups = new Map();
 
  for (const item of items) {
    const key = keyFn(item);
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(item);
  }
 
  return groups;
}
 
const tickets = [
  { id: 1, status: "open" },
  { id: 2, status: "closed" },
  { id: 3, status: "open" },
  { id: 4, status: "pending" },
];
 
groupBy(tickets, (t) => t.status);
// Map { "open" => [ticket1, ticket3], "closed" => [ticket2], "pending" => [ticket4] }

Every item independently figures out its own key and appends itself to that key's bucket. No item's work depends on how many groups exist or how many other items are in them — it's a constant amount of work per item (a map lookup, maybe creating an empty array, an amortized-O(1) push). That's O(n) total for n items, regardless of how many distinct groups the data happens to fall into.

Compare that to the tempting alternative of filtering once per known group:

const open = tickets.filter((t) => t.status === "open");
const closed = tickets.filter((t) => t.status === "closed");
const pending = tickets.filter((t) => t.status === "pending");

With a fixed, small, known set of statuses, this is also O(n) in Big-O terms (three passes is 3n, and Big-O drops the constant 3) — but it's doing three times the real work of one grouped pass, and it stops being expressible at all once the set of statuses isn't known ahead of time. groupBy handles both cases identically, in one pass, without needing to know the groups in advance.

Deduplicating by a key, not by reference

The naive instinct — [...new Set(items)] — only removes exact duplicate references: the literal same object appearing twice in the array. It does nothing for two distinct objects that merely share, say, the same id:

const a = { id: 1, name: "old" };
const b = { id: 1, name: "new, from a later fetch" };
 
new Set([a, b]).size; // 2 — Set sees two different objects, not one duplicate id

This is the same reference-versus-value gotcha from the hash-maps lesson. To deduplicate by a field, key a Map by that field explicitly:

function deduplicateBy(items, keyFn) {
  const seen = new Map();
 
  for (const item of items) {
    const key = keyFn(item);
    if (!seen.has(key)) seen.set(key, item); // keep the FIRST occurrence
  }
 
  return [...seen.values()];
}
 
deduplicateBy([a, b], (item) => item.id); // [{ id: 1, name: "old" }] — one entry, first one kept

One pass, one has() check and one set() per item, each O(1) average — O(n) total, same shape as every other map-based technique in this part of the course. Swapping which occurrence wins (first versus last) is a one-line change: unconditionally overwrite instead of checking has() first, and the last matching item wins instead of the first.

function deduplicateByKeepingLast(items, keyFn) {
  const seen = new Map();
  for (const item of items) {
    seen.set(keyFn(item), item); // no has() check — later items overwrite earlier ones
  }
  return [...seen.values()];
}

Both together: grouping and deduplicating in one real task

A genuinely common frontend job — normalizing an API response that might contain the same record more than once (a paginated feed with overlapping pages, say) while also organizing it by category:

function groupByDeduplicated(items, keyFn, groupFn) {
  const deduped = deduplicateBy(items, keyFn);
  return groupBy(deduped, groupFn);
}

Two sequential O(n) passes — still O(n) overall, the same "sequential linear passes stay linear" argument from the frequency-counting lesson.

What to remember

• groupBy is one linear pass: each item computes its own key and appends to that key's bucket in O(1), for O(n) total regardless of how many distinct groups exist.
• Deduplicating "by reference" (new Set(items)) is different from deduplicating "by a field" — the latter needs a Map keyed explicitly by the chosen field, checked with .has() before insertion.
• Whether the first or last matching item wins is a one-line choice: check has() before setting (first wins) or set unconditionally (last wins).
• Chaining several O(n) map-based passes (dedupe, then group) stays O(n) overall — sequential linear work doesn't compound into anything worse.