Find the Duplicate Number
Problem
Given an array of integers nums containing n + 1 integers, each in the range [1, n] inclusive, there is exactly ONE repeated number. Find it, without modifying the array and using only O(1) extra space.
Examples
Example 1
Input: nums = [1,3,4,2,2]
Output: 2
Explanation: 2 appears twice.
Example 2
Input: nums = [3,1,3,4,2]
Output: 3
Explanation: 3 appears twice.
Constraints
- •
1 <= n <= 10^5 - •
nums.length == n + 1 - •
1 <= nums[i] <= n
Hints
Hint 1
A hash set spotting the first repeated value works in O(n) time — but costs O(n) extra space, which the problem explicitly disallows.
Hint 2
Since every value is in [1, n], each value can be treated as a POINTER to an index — following these pointers repeatedly traces out a path.
Hint 3
Because there's a duplicate, that path must eventually loop back on itself — this is structurally identical to detecting a cycle in a linked list.
Solutions
public int findDuplicateHashSet(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if (!seen.add(n)) return n; // add() returns false if n was already present
}
throw new IllegalArgumentException("No duplicate found");
}Time: O(n) · Space: O(n) — violates the problem's O(1) space requirement