Contains Duplicate
A set answers 'have I seen this before?' in O(1).
Approach
Add each element to a hash set; if an insert finds the value already present, there's a duplicate. Equivalently, compare the size of a set built from the array to the array length. Sorting also works in O(n log n) but the set is faster and clearer.
Time complexity
O(n)
Space complexity
O(n)
Common mistake
Reaching for a nested loop (O(n²)) when a single set pass is both simpler and faster.
See it run, step by step
Generate an interactive lesson for Contains Duplicate — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Contains Duplicate