Contains Duplicate

PracticeNeetCode ↗LeetCode ↗

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

Example

Key Pointers

• A hash set gives O(1) average lookup, turning "have I seen this before" into a single check.
• You only need presence, not counts — a set is enough, no dict required.
• Return the instant a duplicate is found; don't scan the rest of the array.

Step-by-Step Analysis

1. Initialize an empty set seen.
2. For each number n in nums: if n is already in seen, return True immediately.
3. Otherwise add n to seen and continue.
4. If the loop finishes without a repeat, return False.

Complexity

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

Code

def containsDuplicate(nums: list[int]) -> bool:
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False

Code Explanation

How the solution above works, piece by piece.

1. seen = set(): remembers every number looked at so far. Checking x in seen on a set is O(1) on average.
2. for n in nums: one pass, left to right.
3. if n in seen: return True: this number appeared earlier, so there is a duplicate. Stop immediately; no need to look further.
4. seen.add(n): otherwise remember it for later numbers.
5. Loop ends without a repeat → return False. O(n) time, O(n) space for the set.

Visual Walkthrough

Running it on nums = [1, 2, 3, 1]:

Video Explanation

NeetCode — Contains Duplicate, LeetCode 217