LeetCode · #217

Contains Duplicate Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #217

🏗️

Pattern

Hash Set — duplicate detection

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 1

 Input: nums = [1, 2, 3, 1]
Output: true // Because nums[0] == nums[3] == 1 — duplicate found 

Example 2

 Input: nums = [1, 2, 3, 4]
Output: false // All elements are distinct 

Constraints

 • 1 ≤ nums.length ≤ 10⁵ • -10⁹ ≤ nums[i] ≤ 10⁹  ↑ Large range — sorting works, but HashSet gives O(1) per lookup 

Section Two · Approach 1

Brute Force — O(n²)

Compare every element against every other element. Two nested loops — the outer picks one number, the inner checks all subsequent numbers for a match. If any pair is equal, return true.

Why it works

By exhaustively checking every pair (i, j) where j > i, we're guaranteed to find a duplicate if one exists. No element is missed because we cover all possible pairs.

Why we can do better

Problem: For each element, we re-scan the array asking "does this value exist again?" — but a HashSet answers that question in O(1). The inner loop does O(n) work per element that a set lookup eliminates entirely.

Java — Brute Force

 class Solution {
public boolean containsDuplicate(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return true;
                }
            }
        }
return false; // no duplicates found
}
}

Python — Brute Force

 class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True return False # no duplicates 

Metric	Value
Time	O(n²) — every pair checked
Space	O(1) — no extra storage

Section Three · Approach 2

HashSet — O(n)

The question boils down to: "have I seen this number before?" — a membership test. A HashSet tracks every value we've encountered and answers that question in O(1) per lookup.

💡 Mental model: Imagine a bouncer at a concert checking wristbands. Each attendee gets a unique wristband color on entry. When someone walks in, the bouncer glances at the rack of used colors — if that color is already taken, the person is a duplicate. The bouncer doesn't scan the crowd; the rack (your HashSet) gives an instant answer.

Algorithm — One-pass HashSet

Step 1: Create an empty HashSet<Integer>.
Step 2: For each element nums[i], check if it already exists in the set.
Step 3: If set.contains(nums[i]) → return true (duplicate found).
Step 4: Otherwise, add nums[i] to the set and continue.
Step 5: If we exhaust the array without a match → return false.

🎯 When to recognize this pattern:

Any time a problem asks "does a value repeat?", "are all elements unique?", or "find the first duplicate" — think HashSet duplicate detection.
The signal is a membership question over a growing collection.
This same pattern appears in LC 217, LC 219 (Contains Duplicate II with index constraint), LC 128 (Longest Consecutive Sequence), and LC 349 (Intersection of Two Arrays).

Why one pass is enough:

We check before inserting.
If element X appears at indices 3 and 7, when we reach index 7 the set already holds X from index 3 — immediate detection.
We never need to look backward or make a second pass. The set accumulates history as we go.

Section Four · Trace

Visual Walkthrough

Trace through nums = [1, 2, 3, 1]:

One-pass HashSet — all 4 iterations

Notice:

We found the duplicate on the fourth element — meaning we processed 3 elements before detecting it.
In the worst case (no duplicates), we'd scan the entire array building up the set — still O(n).
In the best case (duplicate at position 1), we exit after two elements.

Section Five · Implementation

Code — Java & Python

Java — One-pass HashSet

 import java.util.HashSet;
class Solution {
public boolean containsDuplicate(int[] nums) {
HashSet<Integer> seen = new HashSet<>();
for (int num : nums) {
if (!seen.add(num)) { // add returns false if already present return true;
            }
        }
return false; // no duplicates found
}
}

Python — One-pass set

 class Solution:
def containsDuplicate(self, nums: list[int]) -> bool:
        seen = set()
for num in nums:
if num in seen: # O(1) membership check return True
seen.add(num)
return False # no duplicates 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute Force	O(n²)	O(1)	No extra memory, but too slow for n = 10⁵
Sort + Linear Scan	O(n log n)	O(1)*	In-place sort mutates input; duplicates become adjacent
HashSet ← optimal	O(n)	O(n)	One pass, O(1) per lookup. Space for the set.

Why not sorting?:

Sorting gives O(n log n) and lets you check adjacent elements for duplicates — but it mutates the input array (or costs O(n) to copy first).
The HashSet approach is faster at O(n), doesn't modify the input, and exits early when a duplicate is found.
The trade-off is O(n) extra memory for the set. *O(1) space for sort assumes in-place; O(n) if you copy first to preserve the original.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Negative numbers	`[-1, -2, -3, -1]`	HashSet handles negatives — hash function works the same for all integers.
Zeros	`[0, 0]`	Two zeros are duplicates. The set catches 0 on the second occurrence.
All duplicates	`[5, 5, 5, 5]`	Detected immediately at i=1 — the set already contains 5 from i=0.
Single element	`[1]`	Minimum valid input. A single element can never have a duplicate → `false`.
Large values	`[10⁹, -10⁹, 10⁹]`	No overflow concern — we compare values, never compute sums. HashSet handles extreme ints.
No duplicates	`[1, 2, 3, 4, 5]`	Worst case — we scan the entire array, build a set of size n, and return `false`.

⚠ Common Mistake: Using set.contains() followed by set.add() as two separate calls. In Java, HashSet.add() already returns false if the element was already present — so if (!seen.add(num)) is a single-call shortcut that checks and inserts atomically, avoiding a redundant hash computation.

← Back to Arrays & Hashing problems

LearningTree

LC 217 · Contains Duplicate — Solution & Explanation | DSA Guide