Explanation:The number 2 appears twice in the array.
Example 2:
Input:nums = [3, 1, 3, 4, 2]
Output:3
Explanation:The number 3 appears twice in the array.
Example 3:
Input:nums = [3, 3, 3, 3, 3]
Output:3
Explanation:The number 3 is the only duplicate present in the array.
Constraints:
•
•
•
•
Time Complexity
N/A
Space Complexity
N/A
Step 1 / 12
Speed: 1.0x
Floyd's Cycle Detection (Tortoise and Hare)
Commentary:
Initialize slow and fast pointers to the first node (index 0, value 1).
How it works: We treat the array elements as pointers. Since a duplicate exists, multiple indices point to the same destination, creating a cycle. Slow moves 1 step; Fast moves 2 steps. After they meet (Phase 1), resetting slow to index 0 and moving both at the same speed (Phase 2) identifies the duplicate number at the cycle entrance.