Watch 10 video solutions for Find the Duplicate Number, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCode has 770,501 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and using only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2] Output: 2
Example 2:
Input: nums = [3,1,3,4,2] Output: 3
Example 3:
Input: nums = [3,3,3,3,3] Output: 3
Constraints:
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums appear only once except for precisely one integer which appears two or more times.
Follow up:
nums?Problem Overview: You are given an array nums containing n + 1 integers where each value is in the range [1, n]. Because there are more elements than possible values, at least one number appears more than once. The task is to find that duplicate without modifying the array and using constant extra space.
Approach 1: Floyd's Tortoise and Hare (Cycle Detection) (Time: O(n), Space: O(1))
This approach treats the array as a linked structure where each index points to the next index using its value: next = nums[i]. Because a duplicate value points multiple indices to the same position, the structure forms a cycle. Floyd's cycle detection algorithm (also called tortoise and hare) uses two pointers moving at different speeds to detect that cycle. First, move a slow pointer one step and a fast pointer two steps until they meet. Then reset one pointer to the start and move both one step at a time; the meeting point becomes the duplicate number. This works because the duplicate acts as the entry point of the cycle. The algorithm scans the array only a few times and keeps constant memory, making it the optimal solution using two pointers on top of the array structure.
Approach 2: Binary Search on Result (Time: O(n log n), Space: O(1))
Instead of searching the array indices, binary search can be applied to the value range [1, n]. For a candidate value mid, count how many numbers in the array are <= mid. If the count is greater than mid, the duplicate must lie in the lower half; otherwise it lies in the upper half. This logic comes from the pigeonhole principle: more numbers than allowed in a range implies duplication. Each step scans the array to compute the count, while the search space halves every iteration. The approach keeps constant memory and demonstrates a clever application of binary search on the answer space rather than on indices.
Recommended for interviews: Floyd's Tortoise and Hare is the expected solution. It achieves the required O(n) time and O(1) space while keeping the array unchanged. Explaining the cycle interpretation shows strong algorithmic thinking. The binary search method is still valuable during interviews because it demonstrates reasoning with counting and the pigeonhole principle, but it is slightly slower at O(n log n).
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd's Tortoise and Hare (Cycle Detection) | O(n) | O(1) | Best overall solution when the array cannot be modified and constant memory is required |
| Binary Search on Value Range | O(n log n) | O(1) | Useful when reasoning with counting and pigeonhole principle or when explaining alternative strategies in interviews |