230. Find the Duplicate Number
Medium
Floyd Cycle Detection
Array
Problem
Given an array nums containing n + 1 integers where every integer is in the range 1 to n inclusive, return the single repeated number. The repeated value may occur more than twice.
Examples
Example 1
Input: [1,3,4,2,2]
Output: 2
Example 2
Input: [3,1,3,4,2]
Output: 3
Example 3
Input: [3,3,3,3,3]
Output: 3
Constraints
� 1 <= n <= 100000
� nums.length == n + 1
� 1 <= nums[i] <= n
� Exactly one distinct value is repeated.
Hints
?? Interpret each array value as a pointer to another index.
?? The duplicate creates a cycle in this implicit linked structure.
?? Use Floyd's tortoise-and-hare algorithm to locate the cycle entrance.
Expected Complexity
Time: O(n)
Space: O(1)
Follow-up
Can you solve it without modifying nums and using only O(1) extra space?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[1,3,4,2,2]Expected
2