Contains Duplicate

LeetCode 217: Contains Duplicate Solution & Explanation

Problem Overview

TL;DR: Scan the array once while storing previously seen values in a hash set; if a value is already present, return true, otherwise return false after the scan.

This LeetCode 217 Solution determines whether any integer appears at least twice in nums. The order of elements does not matter, and duplicate occurrences may be at any positions. For the Contains Duplicate problem, the optimal interview solution uses a hash set to perform constant-average-time existence checks.

Because nums.length can be as large as 10^5, checking every pair of elements is inefficient. A previously seen-value set provides a direct way to detect repetition during a single array traversal.

Brute Force Approach for Contains Duplicate

The naive approach compares every element with every element that appears after it:

1. Select an element at index i.
2. Compare it with each element at index j > i.
3. Return true if any pair has the same value.
4. Return false if all pairs are different.

Naive Pseudocode

for i from 0 to n - 1:
    for j from i + 1 to n - 1:
        if nums[i] == nums[j]:
            return true

return false

Complexity

• Time: O(n²), because the algorithm may compare every pair of elements.
• Space: O(1) auxiliary space.

Why the Brute Force Method Fails

With up to 10^5 elements, O(n²) requires up to roughly 10^10 pair comparisons. That is far beyond a practical execution limit and can result in Time Limit Exceeded.

The problem only requires determining whether a value has appeared before. Comparing all pairs performs much more work than necessary because it repeatedly searches for the same information.

Algorithm Strategy: Array/Matrix Manipulation Patterns

1. Create an empty hash set named seen.
2. Traverse each value in nums from left to right.
3. Check whether the current value exists in seen.
4. If it exists, return true immediately.
5. Otherwise, insert the value into seen.
6. If the traversal finishes without finding an existing value, return false.

The hash set enforces uniqueness among the values already processed. A repeated value violates that condition and proves that the array contains a duplicate.

Execution Flow

For nums = [8, 3, 5, 8]:

1. Initialize seen as an empty set.
2. Read 8.
   • 8 is not in seen.
   • Insert 8.
3. Read 3.
   • 3 is not in seen.
   • Insert 3.
4. Read 5.
   • 5 is not in seen.
   • Insert 5.
5. Read 8.
   • 8 is already in seen.
   • Return true immediately.
6. The remaining elements, if any, do not need to be processed.

For nums = [-4, 12, 0, 7], every membership check fails before insertion, so the scan ends and returns false.

Proof of Correctness

We prove that the algorithm returns the correct result.

Invariant

Before processing each array element, seen contains exactly the distinct values that occurred earlier in nums.

Preservation

• If the current value is already in seen, it appeared earlier. Therefore, the array contains a duplicate, and returning true is correct.
• If the current value is not in seen, it has not appeared earlier. Inserting it ensures that seen remains the set of all distinct processed values.

Thus, the invariant is preserved after every iteration.

Termination

If the algorithm completes the entire array without returning true, no value was found in seen before its first insertion. Therefore, every value appeared exactly once, so returning false is correct.

Hence, the algorithm always produces the correct result.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 202: Happy Number
• LeetCode 349: Intersection of Two Arrays
• LeetCode 219: Contains Duplicate II
• LeetCode 3: Longest Substring Without Repeating Characters

Each problem maintains hash-based state to check whether a value, transformed value, or relevant character has already been encountered. The stored information differs, but the core operation remains a previously seen or existence check.

Reference Implementation

C++ Solution for LeetCode 217

1class Solution {
2public:
3    bool containsDuplicate(vector<int>& nums) {
4        unordered_set<int> seen;
5        for (int value : nums) {
6            if (seen.count(value)) {
7                return true;
8            }
9            seen.insert(value);
10        }
11        return false;
12    }
13};

The unordered_set stores values that have already appeared. count(value) checks whether the current value exists before insertion.

Java Solution for LeetCode 217

1class Solution {
2    public boolean containsDuplicate(int[] nums) {
3        java.util.Set<Integer> seen = new java.util.HashSet<>();
4        for (int num : nums) {
5            if (seen.contains(num)) {
6                return true;
7            }
8            seen.add(num);
9        }
10        return false;
11    }
12}

Java’s HashSet provides the previously seen-value storage and supports average constant-time contains and add operations.

Python Solution for LeetCode 217

1class Solution:
2    def containsDuplicate(self, nums: List[int]) -> bool:
3        seen = set()
4        for num in nums:
5            if num in seen:
6                return True
7            seen.add(num)
8        return False

The Python set performs the same existence-check pattern: test membership first, then add unseen values.