DSA problem
Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, there is exactly one repeated number in nums. Return that repeated number. You must solve the problem without modifying the array and using only constant extra space.
The pigeonhole principle guarantees that with n + 1 values drawn from a range of size n, at least one value must repeat. The problem promises that exactly one number repeats (though it may appear more than twice), and asks for that unique duplicate.
The trick that simultaneously satisfies the no-mutation and O(1) space constraints is to interpret the array as a function f(x) = nums[x] mapping positions to positions, then treat the iteration sequence x → f(x) → f(f(x)) → ... as a linked list. Because some index repeats in the array, the iterated sequence must eventually enter a cycle, and the entry point of that cycle is precisely the duplicate value. (Concretely: if v appears at two positions i ≠ j, then f(i) = f(j) = v, so following from index 0 you cannot reach v from anywhere else.)
Floyd's tortoise-and-hare cycle detection then runs in O(n) time using O(1) memory. Phase one advances slow by one step and fast by two steps until they meet inside the cycle. Phase two restarts a pointer at the array's start (index 0) and walks both pointers one step at a time; they converge exactly at the cycle's entry — the duplicate value.
Examples
nums = [1,3,4,2,2]2nums = [3,1,3,4,2]3nums = [1,1]1Constraints
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- All the integers in nums appear only once except for exactly one integer which appears two or more times.
- You must not modify the array nums and you must use only constant extra space.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.