visual walkthrough
Contains Duplicate
Shows the time-vs-space trade-off between sorting and hashing in its simplest form.
The idea
A duplicate exists the moment you meet a number you've already met. A set answers "have I seen this?" in one step, so a single pass is enough.
Comparing every pair does the same job the slow way.
Complexity
| approach | time | space |
|---|---|---|
| Compare every pair | O(n²) | O(1) |
| Hash set | O(n) | O(n) |