Contains Duplicate
The shape of the problem
Return true if any value appears more than once in the array. Any single repeat proves it — you do not need to count.
Signals to notice
Brute force first
Compare every pair: O(n²). Or sort and scan adjacent pairs: O(n log n) and destroys the input order.
The key insight
A hash set gives O(1) expected "have I seen this before?" lookups. That turns an O(n²) scan over pairs into an O(n) scan over elements.
Trace it on nums=[1,2,3,1]
i=0 v=1 1 in {}? no → add set={1}
i=1 v=2 2 in {1}? no → add set={1,2}
i=2 v=3 3 in {1,2}? no → add set={1,2,3}
i=3 v=1 1 in {1,2,3}? YES → return trueWhat must stay true
The set always contains exactly the distinct values from `nums[0..i)`. No duplicate has been missed and no non-duplicate has been wrongly flagged.
Shape of the loop
seen = set() for v in nums: if v in seen: return true seen.add(v) return false
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Adding to the set before the membership check. You then flag every element as a duplicate the second time you look at it, which only matters if you re-scan — easy to write by accident.