The problem
An array nums holds n + 1 integers, each between 1 and n. Exactly one value is repeated (possibly many times). Return it.
The array may not be modified, and only a constant amount of extra memory may be used.
Examples
- Input
nums = [1, 3, 4, 2, 2]
- Output
2
- Input
nums = [3, 1, 3, 4, 2]
- Output
3
- Input
nums = [3, 3, 3, 3, 3]
- Output
3
Constraints
- 1 ≤ n ≤ 10⁵
nums.lengthis n + 1- 1 ≤ nums[i] ≤ n
- Exactly one value appears more than once.
The idea
Read the array as a linked list: from index i go to index nums[i]. Starting at 0 (which no value points to, since values are at least 1), the walk must loop, because there are finitely many indices. The loop is entered at an index that two different positions point to — that index is the repeated value.
Floyd’s algorithm finds a loop’s entrance with O(1) memory. First, slow and fast (one and two steps) meet somewhere inside the loop. Then restart slow at 0 and move both one step at a time: they meet exactly at the entrance. (Why: say the entrance is t steps from 0 and the loop is c long. When they meet, fast has walked twice as far as slow, and the extra distance is whole laps — so slow’s distance, t plus however far it is past the entrance, is a whole number of laps. From the meeting point, then, t more steps land exactly on the entrance.)
- Time
- O(n)
- Space
- O(1) — two indices
Solution · every language run against every case
class Solution: def findDuplicate(self, nums: List[int]) -> int: # Read i -> nums[i] as a linked list; the repeated value is where its loop begins. slow = fast = 0 while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break # From the start and from the meeting point, equal steps reach the loop's entrance. slow = 0 while slow != fast: slow, fast = nums[slow], nums[fast] return slow