LeetCode 217 · Arrays & Hashing

Contains Duplicate, explained with a picture

A stamp collector spots a repeat.

EasyArrays & Hashing
▶ Watch it step by step

The problem

You are given a list of numbers. Return true if any number appears at least twice, and false if every number is different.

Input:  nums = [3, 8, 1, 5, 8, 2]
Output: true   (8 appears twice)

Picture it

Imagine a stamp collector tipping an envelope of stamps into an album, one at a time. Before sticking each stamp in, they glance at the album: “do I already have this one?” In the picture, each stamp is one number from the list and the album is a set: a box that remembers what it has seen and can answer “seen it?” instantly. The moment a stamp is already in the album, we have found a duplicate and can stop.

How to recognise it

  • The question is a plain yes/no about repeats: "does any value appear twice?"
  • You do not need positions or counts, only whether you have seen this value before.
  • One repeat is enough to answer, so you can stop early.
  • The list is not sorted, and n can be up to 10^5, which rules out comparing every pair.
  • "Have I seen this before?" is the textbook question a set answers in O(1).

Start with brute force

Compare every pair of positions (i, j) with i < j. If two hold the same number, there is a duplicate.

def contains_duplicate_brute(nums):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                return True
    return False

There are n(n − 1)/2 pairs, so time is O(n²) and extra space is O(1). LeetCode allows n up to 10^5, which is about 5 × 10^9 comparisons when every number is different: far too slow.

A middle step is to sort first, then compare neighbours: O(n log n) time. It works, but it either changes the input or copies it, and it still does more work than needed.

From brute force to the idea

  1. Find the waste. For each number, the inner loop scans the rest of the list to answer one question: "is there another copy of this value?"
  2. Ask the question the other way round. Instead of looking ahead for a copy, look back: "have I already passed this value?" A copy is always found when its second occurrence arrives.
  3. Remember what you have passed. A set holds the values seen so far and answers x in album in O(1) on average.
  4. Check, then add. For each x, if it is already in the set, return True. Otherwise add it and move on.
  5. Finish the loop. If no value was ever found in the set, every number was different, so return False.

This is the key idea: one pass with a set of values seen so far, stopping at the first repeat.

The key idea

A set answers “have I seen this before?” in one step, so one pass over the list is enough: O(n) time instead of comparing every pair.

Python solution

def contains_duplicate(nums):
    album = set()
    for x in nums:
        if x in album:
            return True
        album.add(x)
    return False

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every pair is compared onceO(1): only two loop indices
Set of seen values (shown code)O(n): one pass, each lookup and insert is O(1) on averageO(n): if all numbers differ, every one is stored

Edge cases

  • Empty list: the loop never runs, so it returns False.
  • One number: returns False; nothing can repeat.
  • Repeat at the very start ([5, 5, 1, 2, 3]): returns True after reading only two numbers. The early return matters on huge inputs.
  • Negatives and zero ([-1, 0, 1, -1]): returns True; a set hashes any integer.
  • All different: the worst case for memory, as the set ends up holding n values.
  • One-liner alternative: len(set(nums)) != len(nums) gives the same answers, but always builds the whole set, even when the repeat is at position 1.

Common mistakes

  • Adding x to the set before checking it. Then every value finds itself, and [1, 2, 3] returns True.
  • Using a list instead of a set for album. x in list scans the list, which quietly brings back O(n²).
  • Sorting and then comparing nums[i] with nums[i + 2] or other non-neighbours. After sorting, equal values are always adjacent, so neighbours are enough.
Your turn: repeats that are close together

Return True if some value appears twice at positions i and j with j − i ≤ k. For [1, 2, 3, 1] with k = 3 the answer is True; for [1, 2, 3, 1, 2, 3] with k = 2 it is False. Describe your approach, then write it if you like.

Compare with our answer

A set no longer says enough: you also need to know where you last saw each value. Store value → last position in a dictionary. When x arrives, check whether its last position is within k, then overwrite it with the current position, because the most recent copy is always the closest one for anything still to come.

def contains_nearby_duplicate(nums, k):
    last = {}                      # value -> most recent position
    for i, x in enumerate(nums):
        if x in last and i - last[x] <= k:
            return True
        last[x] = i
    return False

[1, 0, 1, 1] with k = 1 returns True (the last two 1s). Time O(n), space O(n). (A set that only holds the last k values also works and caps the space at O(k).)

A strong answer mentions: storing positions instead of just values, updating to the most recent position, and why the closest earlier copy is the only one worth checking.

Check what stuck

1. You must report the first value that appears for a second time when reading a list left to right. Which approach fits best?

2. Why does the shown solution run in O(n) time on average?

3. A learner moves album.add(x) above the if x in album: check. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.