Watch 10 video solutions for Find the Duplicate Number, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCode has 439,819 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 receive an array of n + 1 integers where each value is in the range [1, n]. Since there are more numbers than the range allows, at least one value must appear more than once. The task is to return the duplicate number without modifying the array and while using minimal extra space.
Approach 1: Floyd's Tortoise and Hare (Cycle Detection) (O(n) time, O(1) space)
This approach treats the array like a linked list. Each index points to the next index using the value stored at that position. Because values are restricted to 1..n, following these "next" pointers must eventually form a cycle. The duplicate number is exactly the entry point of that cycle. Use two pointers: a slow pointer moving one step at a time and a fast pointer moving two steps. When they meet, a cycle exists. Reset one pointer to the start and move both one step at a time until they meet again; that position corresponds to the duplicate value. This technique uses the classic two pointers pattern and works without modifying the array. Time complexity is O(n) because each pointer traverses the structure at most a few passes. Space complexity is O(1) since only a couple of variables are used.
Approach 2: Binary Search on Result (O(n log n) time, O(1) space)
This method applies binary search on the value range instead of array indices. The key insight comes from the pigeonhole principle. For any midpoint mid, count how many numbers in the array are less than or equal to mid. If the count exceeds mid, the duplicate must lie in the range [1, mid]. Otherwise, it lies in [mid + 1, n]. Repeatedly narrow the search range until a single value remains. Each step scans the array once to compute the count, giving O(n) work per iteration and O(log n) iterations overall. The algorithm uses constant extra memory and does not modify the input.
Recommended for interviews: Floyd's cycle detection is the solution most interviewers expect. It demonstrates deeper algorithmic thinking because you reinterpret the array as a linked structure and apply cycle detection to locate the repeated value. The binary search approach is also valid and easier to reason about, but it is slower at O(n log n). Showing the binary search idea first and then optimizing to Floyd's algorithm signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Floyd's Tortoise and Hare (Cycle Detection) | O(n) | O(1) | Optimal interview solution when array cannot be modified and constant space is required |
| Binary Search on Value Range | O(n log n) | O(1) | Useful when you recognize the pigeonhole principle and want a simpler reasoning approach |