Contains Duplicate: The Hash Set Membership Pattern
Solve Contains Duplicate in O(n) with a hash set — the have-I-seen-it pattern explained with a worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Contains Duplicate looks like the most boring problem on LeetCode: does this array have any repeated value? But it is the cleanest possible demonstration of one idea you will reuse constantly — a hash set turns "have I seen this before?" into an O(1) question.
Get comfortable here and the same reflex fires on anagram checks, cycle detection, deduplication, and any problem where the answer hinges on remembering what already walked past.
The problem
Given an integer array nums, return true if any value appears at least twice, and false if every element is distinct.
Input: nums = [1, 2, 3, 1]
Output: true // the value 1 appears at index 0 and index 3
Input: nums = [1, 2, 3, 4]
Output: false // every value is uniqueTwo things matter about that spec. You only need to know whether a duplicate exists — not which value, not how many, not where. And a single repeat is enough to answer true, so the moment you find one you can stop scanning.
The brute force baseline
The direct reading of "any value appears twice" is: compare every element against every other element.
function containsDuplicate(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] === nums[j]) return true;
}
}
return false;
}This is correct but wasteful. For each element you re-scan the entire remaining array, asking the same question — is this value anywhere else? — from scratch every time. That is n scans of up to n elements each, so O(n²) time. On a 10⁵-element array with no duplicates, that is roughly five billion comparisons before you can even return false.
Sorting first is a second baseline: sort the array, then any duplicate lands next to its twin, so one linear pass over adjacent pairs finds it. That is O(n log n) time and it mutates the input. Better than O(n²), but still not the answer an interviewer wants.
The key insight: remember what you have seen
Flip the question. Instead of asking "is this value somewhere else in the array?" — which forces a search — ask "have I already walked past this value?"
That second question is answerable in O(1) if you keep a running record of everything you have seen. A hash set is exactly that record: add and has both run in average O(1) time. So walk the array once, and at each element check the set before adding to it:
- If the value is already in the set, you have seen it before — that is your duplicate. Return
true. - Otherwise, add it and move on.
This is the membership pattern: a set replaces the inner loop entirely. One pass, constant work per element.
The optimal solution
var containsDuplicate = function (nums) {
const seen = new Set();
for (let i = 0; i < nums.length; i += 1) {
if (seen.has(nums[i])) {
return true;
}
seen.add(nums[i]);
}
return false;
};The order inside the loop is the whole trick: check first, then add. You look up nums[i] in the set before inserting it, so an element can never match itself — it only matches an earlier occurrence. If you added first and checked second, every element would find the copy you just inserted and the function would always return true.
If the loop runs to completion without a hit, no value repeated, so the answer is false.
Walkthrough
Trace nums = [1, 2, 3, 1]. The set starts empty; at each index we check membership, then add.
| i | nums[i] | seen (before) | in set? | Action | seen (after) |
|---|---|---|---|---|---|
| 0 | 1 | {} | no | add 1 | {1} |
| 1 | 2 | {1} | no | add 2 | {1, 2} |
| 2 | 3 | {1, 2} | no | add 3 | {1, 2, 3} |
| 3 | 1 | {1, 2, 3} | yes | return true | — |
At i = 3 the value 1 is already in the set from i = 0, so the membership check hits and the function returns true immediately — it never even looks at whether there were more elements. Notice the loop only reached index 3; on [1, 2, 3, 4] it would run all four iterations, find nothing, and fall through to return false.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n²) | O(1) | n scans of up to n elements each |
| Sort + adjacent scan | O(n log n) | O(1)* | sorting dominates; *mutates input |
| Hash set | O(n) | O(n) | one lookup + one insert per element |
The hash set version makes a single pass with average O(1) work per element, so time is linear. The cost is memory: in the worst case (all distinct values) the set grows to hold all n elements before the loop ends. That is the classic space-for-time trade — you spend O(n) memory to buy an O(n) runtime instead of O(n²).
Common mistakes
- Adding before checking.
seen.add(nums[i])thenseen.has(nums[i])finds the element you just inserted and returnstruefor every array. Always check, then add. - Building a full frequency map. You do not need counts. A set answers presence, which is all the problem asks — and a set is lighter than a
Mapof value → count. - Comparing lengths as the only step, then stopping.
new Set(nums).size !== nums.lengthis a valid and elegant one-liner, but it always allocates a set over the entire array. The explicit loop can early-exit the instant it finds a duplicate, which is faster on inputs where the repeat appears early. - Assuming sorted input. Contains Duplicate gives you an arbitrary array. The adjacent-pair trick only works after you sort, and sorting costs O(n log n) plus mutates the caller's array.
Where this pattern shows up next
The "have I seen it?" set-membership idea is a building block for a whole family of array problems:
- Remove Duplicates from Sorted Array — the sorted cousin, where adjacency lets you dedupe in place with two pointers instead of a set.
- Remove Element — the same in-place, two-pointer overwrite technique applied to a target value.
- Reverse String — another single-pass array primitive, this time with a two-pointer swap.
- Best Time to Buy and Sell Stock — one pass that remembers a running fact (the min so far) to avoid a nested loop, the same trade in a different shape.
You can also step through Contains Duplicate interactively to watch the set fill up and the membership check fire the moment a repeat appears.
FAQ
What is the time and space complexity of Contains Duplicate?
The hash set solution runs in O(n) time and O(n) space. It scans the array once, doing one average-case O(1) has lookup and one add per element. Space is O(n) because the set can grow to hold every element when the array is all distinct. The brute-force nested loop is O(n²) time with O(1) space, and the sort-first approach is O(n log n) time.
Why use a hash set instead of sorting the array?
Sorting solves the problem in O(n log n) and mutates the input, whereas a hash set solves it in O(n) without reordering anything. The set trades O(n) memory for the faster runtime. Sorting only wins when you are memory-constrained and allowed to reorder the array, since it needs no extra structure — but it can never beat the hash set on time.
Why check the set before adding to it?
Because checking first is what makes an element match only its earlier occurrences, not itself. If you add nums[i] and then ask whether the set contains nums[i], the answer is always yes — you just inserted it — so the function would return true for every input, including arrays with no duplicates. Check for membership, and only if it is absent, add it.
Can I solve Contains Duplicate in one line?
Yes: return new Set(nums).size !== nums.length. Building a set from the array drops duplicates, so if the set is smaller than the original array, a duplicate existed. It is clean and correct, but it always processes the entire array to build the set. The explicit loop can return the instant it spots a repeat, which is faster when a duplicate appears early in a large array.
Does the hash set solution handle negative numbers and an empty array?
Yes to both. A JavaScript Set hashes negative integers exactly like positive ones, so [-1, 0, 1, -1] correctly returns true on the second -1. An empty array runs zero loop iterations and falls straight through to return false, which is right — nothing can repeat in an empty array.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.