Given an array of integers, return true if any value appears at least twice and false if every element is distinct.
Before you code
Comparing every pair of elements works, but it takes O(n²) comparisons: about 5 billion for the largest input this problem allows, 100,000 numbers. Sorting first and comparing neighbors takes O(n log n). A hash set gets you to O(n): walk the array once, and for each number ask the set whether it has seen it.
Hints
- A set answers "have I seen this before?" in constant time on average, because it hashes the number to find where it would be.
- You can stop at the first repeat; there is no need to finish the walk.
- Think about the memory: the set may hold up to n numbers. When would the sorting approach be the better choice?
Production & complexity notes
When solving Contains duplicate on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in What a hash function does to reinforce the underlying pattern.
What it practices
Hashing a key to answer a membership question in one step, the idea from What a hash function does.