March 24
Contains Duplicate
How to move away from O(n²) by noticing the problem only asks whether you have seen the value before.
Arrays and Set Beginner 10 min TypeScript
Given an integer array nums, return true if any value appears at least twice, and return false if every element is distinct.
Example:
Input: nums = [1, 2, 3, 1]
Output: true
What to notice before coding
- This is a yes-or-no problem. You do not need full counting.
- As soon as you find a repeated value, you can stop.
- The core question is: have I seen this value before?
Common mistakes
- continuing after finding a duplicate even though the answer is already known
- sorting too early without explaining why that trade-off helps
Step 1 — Read what the problem is actually asking
This is not a full counting problem.
This is not a problem about returning every duplicate.
The prompt only asks whether at least one repetition exists.
That matters because it changes the strategy:
- once you find a duplicate, you are done
- you do not need to keep processing the rest
Step 2 — Write the simplest correct version
The first correct solution compares each number against the later ones:
export function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
if (nums[i] === nums[j]) {
return true
}
}
}
return false
}
It works. But it repeats too much work.
Step 3 — Reframe the question
Instead of asking "which other number matches this one?", the question here is simpler:
has the current number already appeared?
If you could answer that immediately, you would not need the second loop.
Step 4 — Store what you have already seen
A Hash Set solves exactly that part.
While you walk through the array:
- if the value is already in the
Set, a duplicate exists - if not, add it and continue
The whole problem becomes a single pass with memory.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function containsDuplicate(nums: number[]): boolean {
// your solution here
return false
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(n)
Solution 1 — Brute force O(n²)
Use two nested loops. For each number, compare it against the later numbers.
export function containsDuplicate(nums: number[]): boolean {
for (let i = 0; i < nums.length; i += 1) {
for (let j = i + 1; j < nums.length; j += 1) {
if (nums[i] === nums[j]) {
return true
}
}
}
return false
}It works. But it grows too quickly because the array is scanned again and again.
Solution 2 — Hash Set in O(n)
Now the question matches the real need of the problem:
Have I seen this value before?
If that answer is available in constant time, one pass is enough.
export function containsDuplicate(nums: number[]): boolean {
const seen = new Set<number>()
for (const value of nums) {
if (seen.has(value)) {
return true
}
seen.add(value)
}
return false
}The Hash Set stores values that already appeared. When one appears again, you know immediately.
What to say in the interview
A strong short explanation would be:
The baseline compares each number against every later number, so it costs
O(n²). Since I only need to know whether the current value already appeared, I can use aHash Setfor averageO(1)lookup and solve it in one pass.
That shows that you:
- understood the simple version
- explained why it wastes work
- chose the data structure that matches the real question
When this pattern shows up again
The same thinking comes back when the problem asks you to:
- detect repetition
- know whether something has appeared before
- validate uniqueness
- stop early as soon as a condition happens
The point is not memorizing
Hash Set.
The point is noticing when the problem only needs memory of what already passed.