The array nums has n + 1 integers, each between 1 and n inclusive, so at least one value repeats. Exactly one value is repeated (possibly many times). Return that value without modifying the array and using only O(1) extra space.
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- Only one value repeats, but it may repeat more than twice
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
A set finds it in O(n) time but O(n) space, sorting uses O(1) space but changes the array, and counting for every candidate is O(n^2). Treat the array as a linked list where index i points to nums[i]. Because two indices point to the same value, the list has a cycle, and the node where the cycle starts is exactly the duplicate value. Floyd's cycle detection finds a meeting point inside the cycle; then moving one pointer back to the start and stepping both one at a time makes them meet at the cycle entrance.
Algorithm
- Set
slow = nums[0]andfast = nums[nums[0]]. - Move
slowone step andfasttwo steps until they are equal. - Reset
slow = 0. - Move both one step at a time until they meet; that value is the duplicate.
O(n)Space: O(1)<= mid; if more than mid, the duplicate is in the lower half. That is O(n log n) and easier to explain under pressure.class Solution: def findDuplicate(self, nums: List[int]) -> int: # Phase 1: find a meeting point inside the cycle slow, fast = nums[0], nums[nums[0]] while slow != fast: slow = nums[slow] fast = nums[nums[fast]] # Phase 2: find the entrance of the cycle slow = 0 while slow != fast: slow = nums[slow] fast = nums[fast] return slow