Find the Duplicate Number — Step-by-Step Visualization
mediumLeetCode #287ArrayTwo PointersBinary SearchBit Manipulation
Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive. There is only one repeated number in `nums`, return this repeated number. You must solve the problem without modifying the array `nums` and uses only constant extra space.
Algorithm Pattern
Floyd's Cycle-Finding Algorithm (Tortoise and Hare)
Key Idea
Since there is a duplicate number in the range `[1, n]`, if we treat the array elements as pointers to indices (e.g., `nums[0]` points to `index nums[0]`), a duplicate number will necessarily create a cycle. The entrance to this cycle is the duplicate number. We can find this entrance using the two-phase Floyd's algorithm.
Step-by-Step Approach
- Phase 1: Find the intersection point of the slow and fast pointers. Initialize `slow = nums[0]`, `fast = nums[nums[0]]`.
- Move `slow` one step and `fast` two steps until `slow == fast`.
- Phase 2: Find the entrance to the cycle. Reset `slow` to `0` (or `nums[0]`'s starting point logic).
- Move both `slow` and `fast` one step at a time until they meet. The meeting point is the duplicate.
Common Gotchas
- The duplicate number can appear more than twice.
- You cannot modify the array (so no sorting or marking visited).
- Constant extra space is required.