Contains Duplicate

Problem

Given an integer array nums, return true if any value appears at least twice. Return false if every value is distinct.

Examples

Example 1

Input:

nums = [1, 2, 3, 4]

Output:

false

Explanation: every value appears only once.

Example 2

Input:

nums = [1, 2, 3, 1]

Output:

true

Explanation: 1 appears more than once.

Example 3

Input:

nums = [3, 2, 6, -1, 2, 1]

Output:

true

Explanation: 2 appears more than once.

Nature of the Problem

This is a duplicate detection problem.

The important signal is not the order of the numbers. The important signal is whether we have seen a value before.

That makes this problem a natural fit for a set, because a set keeps only unique values and supports fast membership checks.

Analysis

A direct way to solve the problem is to walk through the array from left to right.

For each number, ask one question:

Have I seen this number before?

If the answer is yes, we can stop immediately and return true.

If the answer is no, we store the number in the set and continue.

If we finish the whole array without finding a repeated value, then every element is distinct, so we return false.

Pseudocode

function containsDuplicate(nums) {
    seen = empty set;

    for each number in nums {
        if number exists in seen {
            return true;
        }

        add number to seen;
    }

    return false;
}

Step-by-Step Walkthrough

For:

nums = [1, 2, 3, 1]

Start with:

seen = {}

Read 1:

1 is not in seen
add 1
seen = {1}

Read 2:

2 is not in seen
add 2
seen = {1, 2}

Read 3:

3 is not in seen
add 3
seen = {1, 2, 3}

Read 1 again:

1 is already in seen
return true

Complexity

Time complexity:

O(n)

We inspect each element at most once.

Space complexity:

O(n)

In the worst case, all values are distinct, so the set stores every value.

Key Idea

When a problem asks whether a value appears before, think about memory.

For this problem, the set is that memory: it remembers what we have already seen and lets us detect duplicates as soon as they appear.