Skip to content
Hash map: count and look up

Lesson 4.2

Find duplicates

7 min · 8 steps

  1. Step 1 of 8 · Explanation

    For duplicates there's only one question: "have I seen this number before?" Store every number you pass, and check before storing.

    If you also need where a number first appeared, use a Map from number to index. For [4, 1, 7, 1], 1 is stored with index 1, then the second 1 at index 3 is already in the map, so the result is true. If "seen or not" is enough, use a Set. seen.has(x) and seen.add(x), one step each.

  2. Step 2 of 8 · Predict the result

    What does it return for [3, 3, 3, 5]?

    function solution(nums) {  const seen = new Set()  let dupes = 0  for (const x of nums) {    if (seen.has(x)) dupes++    seen.add(x)  }  return dupes}
    1. 2
    2. 3
    3. 1

  3. Step 3 of 8 · Predict the result

    new Set(nums) drops duplicates. What does it return for [1, 2, 2, 3, 3, 3]?

    function solution(nums) {  const unique = new Set(nums)  return nums.length - unique.size}
    1. 3
    2. 2
    3. 5

  4. Step 4 of 8 · Find the bug

    Problem "Return true if any number appears twice." For [1, 2, 1] this code returns false. Tap the wrong line.

    function solution(nums) {  const seen = new Set()  for (const x of nums) {    if (seen[x]) return true    seen.add(x)  }  return false}

  5. Step 5 of 8 · Arrange the code

    Build a function that removes duplicates but keeps the order of first appearance. [3, 1, 3, 2, 1] becomes [3, 1, 2]. Two lines don't belong.

    const out = []seen.add(x)return [...seen].sort((a, b) => a - b)for (const x of nums) {}if (seen.has(x)) continuereturn out}out.push(x)function solution(nums) {const seen = new Set()if (!seen.has(x)) continue

  6. Step 6 of 8 · Pick the approach

    "Return the first letter that shows up for the second time." Constraints: 1 ≤ s.length ≤ 10⁵.
    Which approach is right?

    1. One pass with a Set. Return the letter that's already in the Set
    2. For each letter, check s.indexOf(ch) !== s.lastIndexOf(ch)
    3. Sort the letters, then look for two equal neighbors

  7. Step 7 of 8 · Write the code

    solution(nums)

    Return the first number that appears for the second time (the one whose second copy comes earliest). If there isn't one, return null.
    Constraints: 0 ≤ nums.length ≤ 10⁵.

    function solution(nums) {  // [2, 5, 1, 5, 2] -> 5 }

  8. Step 8 of 8 · Recap

    • "Seen it before?" is answered by a Set. If you need the index, use a Map.
    • Check first, then store. Flip it and every item looks like a duplicate.
    • Sets and Maps are read with .has and .get, not square brackets.

    Pattern card

    A Set for "seen it before"
    When to use it: When a problem mentions duplicates, unique, repeated, or "appears again".
    const seen = new Set()for (const x of nums) {  if (seen.has(x)) return x  seen.add(x)}