Find the Duplicate Number - Solution
Solutions and explanations
In this approach, we treat the array as a linked list where each index points to the value at that index. If there is a duplicate, it creates a cycle in this hypothetical linked list.
Now, we solve this problem in two phases:
-
Phase 1: Detecting the cycle
- Both pointers start at the beginning of the array, but one pointer (slow) moves one step at a time, while the other (fast) moves two steps at a time.
- If a cycle exists (caused by the duplicate), the two pointers will definately meet inside the cycle.
-
Phase 2: Finding the start of the cycle
- Once the slow and fast pointers meet inside the cycle, we introduce another pointer (slow1) starting from the beginning of the array, while keeping slow at the meeting point.
- We then move both slow and slow1 one step at a time.
- Now, the point where the slow and slow1 pointers meet is the duplicate number.
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# Phase 1: Find intersection point
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 1: Find entrance to the cycle
slow1 = 0
while slow != slow1:
slow = nums[slow]
slow1 = nums[slow1]
return slow
Complexity Analysis
This approach runs in O(n) time, uses O(1) space, and does not modify the array.