254. Find the Duplicate Number
You are given an array nums of n + 1 integers, each between 1 and n inclusive. With more slots than distinct values, the pigeonhole principle forces a collision — and in this array exactly one value is repeated (it may occur two times or more; every other value occurs at most once). Return that repeated value.
The classic challenge attached to this problem: find it without modifying the array and using only constant extra space. A hash set or a sort gets the right answer, but each one breaks one of those two rules.
Example 1:
Input: nums = [1, 3, 4, 2, 2]
Output: 2
Explanation: n = 4 and the values 1, 3, 4 appear once each while 2 appears twice.
Example 2:
Input: nums = [3, 1, 3, 4, 2]
Output: 3
Explanation: 3 is the only value that shows up in two slots.
Constraints:
- 1 ≤ n ≤ 10⁵
- nums.length == n + 1
- 1 ≤ nums[i] ≤ n
- Exactly one value is repeated; it may appear two or more times.
Hints:
The first idea: remember what you have seen. A hash set spots the first revisited value in one pass — correct, but it spends O(n) memory.
Count instead of remember: let count(x) be how many entries are <= x. For x below the duplicate, count(x) <= x; from the duplicate upward, count(x) > x. That boundary is monotone, so binary search the value range 1..n.
Read i -> nums[i] as an arrow between positions. Because values live in 1..n and position 0 is never pointed at, the walk from index 0 enters a cycle, and the cycle's entrance is exactly the repeated value. Floyd's tortoise-and-hare finds it with two pointers and no extra memory.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 4, 2, 2]
Expected output: 2