Contains Duplicate

1. Define the problem

Given an integer array nums, return true if any value appears at least twice , and false if every element is different. Keep a hash set of the numbers you have already walked past. For each new number, first ask the set whether it is already in there. If it is, you have found a repeat and can stop immediately. If it is not, put it in the set and move on. Asking a set whether it holds a value costs about the same tiny amount of time however many values it holds, which is why this beats comparing every pair.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁹ ≤ nums_i ≤ 10⁹

Example

Inputnums = [1, 2, 3, 1]

Outputtrue

Explanation The value 1 appears at index 0 and again at index 3, so there is a duplicate.

2. Know the words first

In plain terms

Hash set: A bag of values that answers one question very fast: "is this value already in here?" It never stores the same value twice.
Duplicate: The same value appearing more than once in the array, no matter how far apart the two copies are.

3. Visualize the solution

Each cell is a slot in the hash set, filled as numbers are added

slot 0—

slot 1—

slot 2—

slot 3—

Statusinit

The hash set starts empty, so every slot shows a dash.

What happens in this step

nums = [1, 2, 3, 1]
seen = empty

Nothing has been walked past yet.
The four slots stand for the values the set may end up holding.

Step 1 of 6

Steps to visualize

The cells below are the hash set. A dash means that slot is still empty.
Walk the array one number at a time.
Before storing a number, ask the set whether it is already there.
If the set says yes, the answer is true and you can stop early.
If the set says no, add the number and carry on.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Each cell is a slot in the hash set, filled as numbers are added

slot 0—

slot 1—

slot 2—

slot 3—

Statusinit

The hash set starts empty, so every slot shows a dash.

What happens in this step

nums = [1, 2, 3, 1]
seen = empty

Nothing has been walked past yet.
The four slots stand for the values the set may end up holding.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function containsDuplicate(nums) {
  const seen = new Set();

  for (const num of nums) {
    if (seen.has(num)) {
      return true;
    }

    seen.add(num);
  }

  return false;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3, 1]`	`true`	example from the description
`nums = [1, 2, 3, 4]`	`false`	every value is unique
`nums = [7]`	`false`	smallest input, one element cannot repeat
`nums = [-1, -1]`	`true`	negative numbers repeating
`nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 1]`	`true`	longer array where the repeat is only found at the end
`nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]`	`true`	several different values repeat

Contains Duplicate