Algorithms & Scaling

Big-O describes how work grows with input size, not exact milliseconds. Checking every candidate against every allowed value with repeated linear searches can do roughly n*m comparisons. Building a Set once provides efficient membership queries in typical implementations, with a cost for building and retaining the index.

Choose an algorithm only after preserving behavior. Sets use SameValueZero equality: object keys compare by identity, and NaN can match NaN. If your old logic used normalized string comparison, normalize before building the set. Otherwise a faster implementation can quietly change the contract.

For small lists, setup overhead may dominate; do not conclude that every includes call needs a Set. The relevant question is whether repeated membership queries justify an index. The example uses controlled primitive IDs and preserves candidate order.

Predict, run, and explain

Write the output and trace the important state changes before checking it. Then run the program. Each editor is independent. Async examples end with main() so this editor waits for their work.

const allowed = new Set(["a", "c"]);
const candidates = ["c", "b", "a"];

console.log(candidates.filter(id => allowed.has(id)).join(","));
console.log(allowed.size);

c,a
2

Separate membership indexing from deduplication

A membership index accelerates repeated questions about allowed ids. It need not remove duplicates from the candidate sequence. Changing which side is iterated can alter both order and repeated values even when every returned id is allowed.

Account for index construction and retained memory as well as lookup work. A one-off query on a tiny list may not justify building a Set. Use growth and repeated-query behavior to decide, rather than treating a particular collection as universally faster.

const allowed = new Set(["a", "b"]);
const candidates = ["b", "a", "b", "c"];

console.log(candidates.filter(id => allowed.has(id)).join(","));
console.log([...new Set(candidates)].filter(id => allowed.has(id)).join(","));

b,a,b
b,a

The second variant deduplicates candidates, changing the contract. It is not simply a faster implementation of the first if repeated candidates are meaningful.

const first = { id: "a" };
const second = { id: "a" };
const objects = new Set([first]);
const ids = new Set([first.id]);

console.log(objects.has(second));
console.log(ids.has(second.id));

false
true

Object membership uses identity; id membership uses the domain key. An optimization that switches representation must preserve the comparison semantics the original behavior required.

Try the rule on new inputs

Test candidate order, duplicate candidates, empty allowed sets and normalized ids. Describe repeated linear searches in terms of candidate count and allowed count before measuring a particular machine.

Your turn

// A membership index and output deduplication are different operations.

function selectAllowed(candidates, allowedIds) {
  const allowed = new Set(allowedIds);

  return candidates.filter(id => allowed.has(id));
}

console.log(selectAllowed(["b", "a", "b", "c"], ["b", "c"]).join(","));

b,b,c

Change it and test it

Test empty inputs, duplicate allowed IDs and duplicate candidates. Compare the result with a simple includes-based reference implementation across several small cases. Explain the index’s extra memory cost and why result order still follows candidates.