Floyd’s Cycle Detection (Tortoise and Hare)

Video explanation

Use two pointers:

• slow moves one step at a time.
• fast moves two steps at a time.

If a cycle exists, they meet. Reset one pointer to the start and move both one step at a time to find the cycle entrance. Time $O(n)$, space $O(1)$.

Problem: Find the Duplicate Number

LeetCode 287 — Find the Duplicate Number

Treat each index as a node and nums[index] as its next pointer. The duplicate is the cycle entrance.

function findDuplicate(nums) {
  let slow = 0;
  let fast = 0;
 
  // Phase 1: find an intersection inside the cycle.
  while (true) {
    slow = nums[slow];
    fast = nums[nums[fast]];
    if (slow === fast) break;
  }
 
  // Phase 2: find the entrance to the cycle (the duplicate).
  let slow2 = 0;
  while (true) {
    slow2 = nums[slow2];
    fast = nums[fast];
    if (slow2 === fast) break;
  }
 
  return slow2;
}

Does not modify nums; time $O(n)$, space $O(1)$.