Contains Duplicate Solution Explained – Step-by-Step

Data Structures / Array

Contains Duplicate

Easy

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.

Example

Input: nums = [1,2,3,1]
Output: true
Explanation: The value 1 appears twice.

Input: nums = [1,2,3,4]
Output: false
Explanation: All values are distinct.

Explanation

The most efficient approach to solve this problem is using a hash set to track which numbers we've seen. A hash set provides O(1) average time complexity for both insertions and lookups.

We iterate through the array once, and for each element:

Check if the number already exists in our set
If yes, we found a duplicate — return true
If no, add the current number to the set
If we finish the loop without finding duplicates, return false

This approach works because a set can only contain unique values. When we try to check if a number exists before adding it, we instantly know if we've seen it before.

Idea Map

Start

Create empty seen = {}

For each num in nums

1. If num in seen
Return true
2. Else: seen.add(num)

After loop: Return false

End

Complexity Analysis

Time Complexity

O(n) - We traverse the array once, and each hash set lookup/insertion is O(1) on average.

Space Complexity

O(n) - In the worst case (all distinct elements), we store all n elements in the set.

Code


def containsDuplicate(nums):
Initializes the function `containsDuplicate` which takes the array `nums` as input.
    seen = set()
Creates an empty set to store unique numbers we've encountered for O(1) lookups.
    for num in nums:
Loops through each number in the input array.
        if num in seen:
Checks if the current number already exists in our set (we've seen it before).
            return True
If the number is already in the set, we found a duplicate — return True immediately!
        seen.add(num)
If not seen before, add the current number to the set for future lookups.
    return False
If we finish the loop without finding any duplicates, return False.


public boolean containsDuplicate(int[] nums) {
Initializes the function `containsDuplicate` which takes the integer array `nums` as input.
    Set<Integer> seen = new HashSet<>();
Creates a HashSet to store unique integers we've encountered for O(1) lookups.
    for (int num : nums) {
Enhanced for-each loop that iterates through each integer in the array.
        if (seen.contains(num)) {
Checks if the current number already exists in our set using the contains method.
            return true;
If the number is already in the set, we found a duplicate — return true immediately!
        }
End of the if statement.
        seen.add(num);
If not seen before, add the current number to the set for future lookups.
    }
End of the for-each loop.
    return false;
If we finish the loop without finding any duplicates, return false.
}
End of the function.


bool containsDuplicate(vector<int>& nums) {
Initializes the function `containsDuplicate` which takes a reference to the vector `nums` as input.
    unordered_set<int> seen;
Creates an unordered_set (hash set) to store unique integers for O(1) lookups.
    for (int num : nums) {
Range-based for loop that iterates through each integer in the vector.
        if (seen.find(num) != seen.end()) {
Checks if the current number exists in our set (find doesn't return end()).
            return true;
If the number is already in the set, we found a duplicate — return true immediately!
        }
End of the if statement.
        seen.insert(num);
If not seen before, insert the current number into the set for future lookups.
    }
End of the for loop.
    return false;
If we finish the loop without finding any duplicates, return false.
}
End of the function.

Edge Cases & Common Mistakes

⚠️

Empty or single-element arrays

An array with 0 or 1 elements can never have duplicates. Our algorithm handles this correctly by returning false (never finds a duplicate).

💡

Early exit optimization

We return as soon as we find the first duplicate. This is optimal — no need to continue checking once we know the answer.

✓

Negative numbers and zeros

The hash set approach handles negative numbers, zeros, and positive numbers all the same way — no special cases needed.

What is a Hash Set?

A hash set is a data structure that implements a mathematical set, which stores unique elements. It provides constant-time O(1) average case for insertions, deletions, and lookups by using a hash function to compute an index into an array of buckets.

Learn more about hash tables →

lightbulb

Disclaimer: This problem is for educational purposes. Practice the 'Contains Duplicate' problem on LeetCode.

AlgoExplained.dev