Skip to the content
Start

Project: find duplicates fast

JavaScript · Unit 21: Complexity

Telling whether a list carries duplicates can be done two ways: comparing every pair, O(n²), or writing down what you have already seen in a Set, O(n).

You are going to write the second one.

const ns = [4, 7, 4];
const seen = new Set();
let found = false;
for (const x of ns) {
  if (seen.has(x)) {
    found = true;
  }
  seen.add(x);
}
console.log(found);

Prints

true

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

  1. 1. Predict the output

    This is the slow way: it counts the comparisons with 6 items. What does it print?

  2. 2. Complete the code

    Complete it so it only warns you when the value had already shown up.

  3. 3. Write the code

    Write hasDuplicate(items): it gives back true if some value shows up twice, and false if all of them are different. Walk the array once and lean on the Set. With an empty array it is false.

  4. 4. Write the code

    Now firstDuplicate(items): instead of true, give back the first value that had already shown up; if all of them are different, give back null. It is the same walk, changing what you return.

Do this lesson

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.

See all lessons →