two-pointer • Intermediate

Fast and Slow Pointers (Floyd's Cycle Finding Algorithm)

Two pointers moving at different speeds (slow by 1 step, fast by 2 steps) detect cycles and find middle elements in linear O(N) time with O(1) space.

Intuitive Mental Model

The Runners on a Circular Track: If two runners jog on a circular running track where one runs twice as fast as the other, the faster runner is mathematically guaranteed to lap and meet the slower runner.

C / TypeScript ImplementationHardware & Algorithmic Standard

function findDuplicate(nums: number[]): number {
  let slow = nums[0];
  let fast = nums[0];

  // Phase 1: Detect cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Phase 2: Find cycle entrance
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }
  return slow;
}

Key Architectural Takeaways

•Cycle Detection: Fast and slow pointers meet inside the cycle in O(N) time.
•Middle of Array/List: When fast reaches the end, slow is precisely at the midpoint N/2.

Common Coding Mistake

Using hash sets for cycle detection on memory-constrained systems, wasting O(N) auxiliary RAM.

Optimal Solution

Use Floyd's fast and slow pointer algorithm for O(1) space.

Next: Sliding Window Technique: Fixed vs Dynamic Windows