Contains Duplicate

The problem

Given a list of integers nums, return true if any value appears at least twice, and false if every value is different. An empty list has no duplicates, so it returns false.

What to write

function solve(nums: number[]): boolean

Input
nums = [1,2,3,1]

Output
true

Input
nums = [1,2,3,4]

Output
false

Constraints

0–10,000 integers; values from -1,000,000 to 1,000,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list can hold 10,000 values. Comparing every value with every other one is about 50 million comparisons, so aim to look at each value once.

2. Hint 2: Ask a smaller question

   You are looking at one value in the middle of the list. What would you need to know about the values before it to say "this is a duplicate" right away?

3. Hint 3: Name the pattern

   You need a fast answer to "have I seen this value before?". A hash set gives it: adding a value and checking for one each take about one step. This is hash set membership. Read the lesson on hash set membership.

4. Hint 4: State the invariant

   Before you look at a value, the set holds exactly the values that came before it. So the value is a duplicate exactly when it is already in the set.

5. Hint 5: Sketch the pseudocode

   Start with an empty set. For each value: if it is in the set, return true; otherwise add it. If the loop ends, return false.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Walk through the values and keep the ones already seen in a set. A value that is already in the set is a duplicate.

The slow way

Compare every value with every value after it and return true at the first match. It is correct, but with 10,000 values that is about 50 million comparisons: the work grows with the square of the list's length.

The insight

You do not have to compare a value with all the others. You only have to know whether it has appeared before, and a set can answer that in one step if you fill it as you go.

Step by step

1. Keep a set of the values seen so far. A set answers "have I seen this value?" in about one step, however many values it holds.
2. A value that is already in the set is a duplicate. The set holds exactly the earlier values, so finding the current one there means it appeared before. You can stop at once.
3. Otherwise remember it and move on. The value has to be in the set before the next one is checked, or a later copy of it would go unnoticed.
4. Every value was new, so nothing repeats. Reaching the end means each value was added once and never found, so the list has no duplicate.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Keep a set of the values seen so far
  const seen = new Set();
  for (const num of nums) {
    // 2. A value that is already in the set is a duplicate
    if (seen.has(num)) return true;
    // 3. Otherwise remember it and move on
    seen.add(num);
  }
  // 4. Every value was new, so nothing repeats
  return false;
}

function solve(nums: number[]): boolean {
  // 1. Keep a set of the values seen so far
  const seen = new Set<number>();
  for (const num of nums) {
    // 2. A value that is already in the set is a duplicate
    if (seen.has(num)) return true;
    // 3. Otherwise remember it and move on
    seen.add(num);
  }
  // 4. Every value was new, so nothing repeats
  return false;
}

def solve(nums):
    # 1. Keep a set of the values seen so far
    seen = set()
    for num in nums:
        # 2. A value that is already in the set is a duplicate
        if num in seen:
            return True
        # 3. Otherwise remember it and move on
        seen.add(num)
    # 4. Every value was new, so nothing repeats
    return False

Example 1, traced

Input
nums = [1,2,3,1]

Output
true

Why it works

The set always holds exactly the values before the current one. If the current value is in it, the same value appeared earlier, which is a duplicate. If the loop finishes, no value was ever found there, so all of them are different.

Time and space

Time O(n) expected, extra space O(n). Each value is checked and added once. In a hash set both take about one step on average, which is what "expected" means, so the time is O(n). In the worst case every value ends up in the set, so the space is O(n) too.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Check before you add. If you add the value first and then look for it, every value finds itself, and any list that is not empty returns true.
• Sorting the list to bring equal values together also works, but it is slower and it changes the order of the input.

Pattern

Hash set membership.

Keep going