197. Contains Duplicate
You receive an array of integers nums. Report whether the array repeats itself anywhere: return true if some value occurs two or more times, and false if every element is distinct.
That's the whole task — but the interesting part is doing it without comparing every element against every other element. What structure lets you ask "have I met this value before?" in constant time?
Example 1:
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The value 1 shows up at index 0 and again at index 3, so the answer is true.
Example 2:
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: All four values are different, so no duplicate exists.
Example 3:
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true
Explanation: Several values repeat (1, 3, 4, and 2), so the answer is true.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
Hints:
Comparing every pair works but costs O(n²). Can you make repeated values land next to each other instead?
After sorting, duplicates are always adjacent — one linear scan finds them.
A hash set remembers everything you've seen with O(1) lookups: the first time an insert finds the value already present, you're done.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 3, 1]
Expected output: true