Find The Duplicate Number
Find the duplicate in an array of n+1 integers in range [1, n] using Floyd's cycle detection on indices.
Problem#
nums has length n+1 with values in [1, n]. Exactly one value is duplicated (possibly many times). Find it without modifying the array and in O(1) extra space.
Examples#
[1,3,4,2,2]→2[3,1,3,4,2]→3
Constraints#
1 <= n <= 10^5.
Hints#
Hint 1
nums[i] as a pointer from index i to index nums[i]. Duplicates create a cycle. Approach#
Floyd’s. Phase 1: tortoise-hare on f(i) = nums[i] find their meeting point inside the cycle. Phase 2: reset one pointer to the start; advance both at speed 1; they meet at the cycle entry — which equals the duplicated value.
Solution#
class Solution {public: int findDuplicate(vector<int>& nums) { int slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }};func findDuplicate(nums []int) int { slow, fast := nums[0], nums[0] for { slow = nums[slow] fast = nums[nums[fast]] if slow == fast { break } } slow = nums[0] for slow != fast { slow = nums[slow] fast = nums[fast] } return slow}from typing import List
class Solution: def findDuplicate(self, nums: List[int]) -> int: slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slowvar findDuplicate = function(nums) { let slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast); slow = nums[0]; while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; } return slow;};class Solution { public int findDuplicate(int[] nums) { int slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = nums[0]; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }}function findDuplicate(nums: number[]): number { let slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow !== fast); slow = nums[0]; while (slow !== fast) { slow = nums[slow]; fast = nums[fast]; } return slow;}Editorial#
The array defines a functional graph where every node has out-degree 1. With values in [1, n] and length n+1, by pigeonhole there must be two indices mapping to the same value — i.e., the graph has at least one node with in-degree ≥ 2, which is the entry to a cycle. Floyd’s tortoise-and-hare finds the cycle, and the standard distance lemma (sum of distances from start = sum around cycle) implies that resetting one pointer to the start and advancing both at speed 1 lands on the entry node.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#