LeetEye LeetEye
Easy Hash Set / Hash Map ~5 min

Contains Duplicate

arrays-and-hashing contains-duplicate

Problem

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

Examples

Example 1
Input: nums = [1, 2, 3, 1]
Output: true
1 appears twice
Example 2
Input: nums = [1, 2, 3, 4]
Output: false
All elements are distinct
Example 3
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true
Key Insight

The bottleneck is the "have I seen this?" lookup.

When you need to answer 'have I seen this before?' in O(1), use a hash set.

How to Approach This Problem

Pattern Recognition: When you see keywords like contains duplicate arrays-and-hashing, think Hash Set / Hash Map.

Step-by-Step Reasoning

1 What is the core operation you need to perform for each element?
Answer: Check if you've seen it before
The problem asks if ANY value appears twice. You don't need counts, positions, or adjacent comparisons. You just need to know: seen or not seen.
2 If you check each element against all previous elements, what's the time complexity?
Answer: O(n²)
For each of n elements, you potentially scan all previous elements. First element: 0 comparisons, second: 1, third: 2, ... nth: n-1. Total: 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)
3 What operation needs to be faster to improve the solution?
Answer: Checking if an element was seen before
Iteration is already O(n) - you must look at each element once. The bottleneck is that for each element, you're doing O(n) membership check. Make that O(1), and you get O(n) overall.
4 Which data structure provides O(1) average membership checking?
Answer: Hash Set
Hash sets use hashing to achieve O(1) average insert and lookup. Arrays need O(n) scan, linked lists need O(n) traversal, BSTs need O(log n) traversal.
5 Complete the algorithm:
1. Create empty hash set
2. For each number in array:
a. If number is in set → ___
b. If number is not in set → ___
Answer: return true; add to set
If you find the number already in the set, you've found a duplicate → return true immediately. Otherwise, add it to track it for future checks.
6 What should the function return if the loop completes without finding a duplicate?
Answer: false
If you check every element and never find one already in the set, all elements are unique → no duplicate exists → return false.

Solution

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

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Hash Set / Hash Map problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye