ASAPUtils
The signal
“Does any value appear twice?” is the purest form of have I seen this before? — and that question has exactly one good answer: a hash set. There’s no ordering requirement, no index in the output, nothing positional at all. That’s your cue that you can throw away position entirely.
Approach ladder
1. Brute force — O(n²)
Compare every pair with a double loop. Correct, and with n ≤ 10⁵ in the constraints it will
time out. Say it, price it, move on.
2. Sort first — O(n log n) time, O(1) extra space
Duplicates become adjacent once sorted, so one pass over neighbours finds them. This is a genuinely good answer when memory matters, and worth mentioning as the space-optimal option.
3. What is the brute force wasting?
It re-scans elements it has already visited. Re-scanning for something you’ve already seen is the textbook signal for a hash set.
4. Optimal — O(n)
One pass. For each value, ask the set; if it’s there you’re done, otherwise add it and continue.
Note that this exits early — on [1, 1, 2, 3, …, 10⁵] it stops at index 1, where the sorting
solution still pays the full O(n log n).
Walkthrough
On [1, 2, 3, 1]:
| i | value | set before | action |
|---|---|---|---|
| 0 | 1 | {} | not seen → add 1 |
| 1 | 2 | {1} | not seen → add 2 |
| 2 | 3 | {1,2} | not seen → add 3 |
| 3 | 1 | {1,2,3} | seen → return true |
Complexity
- Time O(n) — one pass, O(1) average per set operation, with early exit.
- Space O(n) — the set holds up to
nvalues.
Traps
- Adding before checking. Then every element finds itself and you always return true.
- Using a plain
{}in JavaScript. Numeric keys get stringified;Setis the right tool. - Claiming O(1) space for the sorting version without qualifying it.
sort()on a JS array is in place, but many sort implementations use O(log n) stack.
Blank re-solve prompt
Given an integer array, return whether any value appears more than once. One pass. No hints.