Fast & Slow Pointers
LC #287Medium
Find the Duplicate Number
Fast & Slow Pointers
AmazonGoogleMetaProblem
Find the duplicate in an array of n+1 integers where each integer is in [1, n]. Must not modify the array and use O(1) space.
arrayfast-slow-pointersbinary-search
Constraints
- ›2 ≤ n ≤ 10⁵ (array length n+1)
- ›Each integer is in range [1, n]
- ›Exactly one duplicate (may appear more than twice)
- ›Must not modify the array; O(1) extra space
Example
Input
nums = [1, 3, 4, 2, 2]Output
2Why
2 appears twice; all other numbers appear exactly once