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?The key challenge in Find the Duplicate Number is identifying a repeated value in an array of n + 1 integers where each number is within the range 1..n, while keeping space usage minimal and avoiding modification of the array. A powerful way to think about the problem is by interpreting the array as a linked structure, where each index points to the value at that index. Because a duplicate exists, this structure forms a cycle. Using Floyd’s Tortoise and Hare (two pointers) technique allows you to detect the cycle and locate the duplicate efficiently.
Another perspective is applying binary search on the value range rather than indices. By counting how many numbers are less than or equal to a midpoint, you can determine which half of the range must contain the duplicate using the pigeonhole principle. Some solutions also use bit manipulation to reconstruct the duplicate number bit by bit by comparing bit frequencies.
The cycle detection approach is typically preferred because it runs in O(n) time and O(1) extra space without modifying the input.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Floyd’s Cycle Detection (Two Pointers) | O(n) | O(1) |
| Binary Search on Value Range | O(n log n) | O(1) |
| Bit Manipulation Counting | O(n log n) | O(1) |
NeetCode
This approach uses cycle detection to find the duplicate number using two pointers. Imagine the numbers in the array form a linked list, where the value at each index points to the next index. When there is a duplicate, a cycle will be formed. The first step is to find the intersection point of the cycle using a slow and fast pointer. Once they meet, use two pointers to find the entrance of the cycle, which will be the duplicate number. This method doesn't modify the array and uses O(1) space.
Time Complexity: O(n), where n is the size of the array. Space Complexity: O(1), since we use a constant amount of extra space.
1
2public class Solution {
3 public int findDuplicate(int[] nums) {
4 int slow = nums[0];
5This Java solution applies the cycle detection method, with slow and fast pointers. It first finds a point within the cycle and then determines the duplicate by resetting and moving one pointer.
This approach leverages a binary search technique on the range of possible values of the duplicate number. For each midpoint in this range, count how many numbers are less than or equal to it. If the count is greater than the midpoint, the duplicate must be in the lower range; otherwise, it is in the upper range. Binary search is applied until the duplicate is found. This doesn't require additional space and doesn't alter the input array.
Time Complexity: O(n log n). Space Complexity: O(1).
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, binary search can be applied to the value range rather than the array indices. By counting how many numbers are less than or equal to the midpoint, you can determine whether the duplicate lies in the lower or upper half using the pigeonhole principle.
Yes, this problem is commonly asked in FAANG and other top tech company interviews. It tests knowledge of cycle detection, pointer techniques, and reasoning about constraints like constant space and immutable arrays.
The optimal approach uses Floyd’s Tortoise and Hare cycle detection algorithm. By treating array indices and values as pointers, the duplicate creates a cycle that can be detected using two pointers. This method runs in O(n) time and O(1) space without modifying the array.
Since the array contains n+1 numbers in the range 1..n, at least one value must repeat. Interpreting each value as a pointer to the next index forms a linked structure where the duplicate creates a cycle. Floyd’s algorithm detects and locates the entry point of this cycle.
This C solution uses binary search on the range of possible numbers, counting numbers less than or equal to the midpoint, and then adjusting the binary search boundaries accordingly, eventually discovering the duplicate number.