The Tortoise and the Hare: Fast & Slow Pointers

Imagine a race between a tortoise and a hare on a circular track. The hare runs twice as fast as the tortoise. What happens? They WILL meet again!

What Are Fast & Slow Pointers?

Think of two friends walking on a path:

• Slow friend: Takes 1 step at a time
• Fast friend: Takes 2 steps at a time

Simple Rule:

• If the path has a LOOP, they will meet inside it
• If the path ENDS, the fast friend reaches the end first

let slow = head;
let fast = head;

while (fast && fast.next) {
  slow = slow.next;      // 1 step
  fast = fast.next.next; // 2 steps
}

Why Does This Work?

The Magic:

When there’s a loop, the fast pointer enters it first. The slow pointer follows. Since fast moves 2x speed, it “catches up” from behind!

graph TD
    A[Start] --> B[Fast enters loop first]
    B --> C[Slow enters loop]
    C --> D[Fast catches up to Slow]
    D --> E[They Meet!]

Real Life Example:

Imagine running on a circular track:

• You run at normal speed
• Your friend runs twice as fast
• Even though they’re ahead, they’ll lap you and meet you!

Problem 1: Linked List Cycle II

The Challenge

Find WHERE a cycle begins in a linked list.

The Story

Imagine you’re lost in a maze. You find a loop, but you need to find the ENTRANCE to that loop!

How It Works

Step 1: Find where tortoise and hare meet (inside the loop)

Step 2: Put one pointer back at the start

Step 3: Move BOTH at same speed - they meet at the entrance!

function detectCycle(head) {
  let slow = head;
  let fast = head;

  // Find meeting point
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) break;
  }

  // No cycle
  if (!fast || !fast.next) return null;

  // Find entrance
  slow = head;
  while (slow !== fast) {
    slow = slow.next;
    fast = fast.next;
  }

  return slow; // Cycle starts here!
}

Why Does Step 2 Work?

graph LR
    A[Head] -->|x steps| B[Cycle Start]
    B -->|y steps| C[Meeting Point]
    C -->|z steps| B

The Math Magic:

• Distance from head to cycle start = x
• When they meet, slow traveled x + y
• Fast traveled 2(x + y)
• The difference is the cycle length!
• Moving from head and meeting point at same speed = they meet at cycle start!

Problem 2: Happy Number

The Challenge

Is a number “happy”? A happy number eventually reaches 1 when you keep replacing it with the sum of squares of its digits.

The Story

Think of a number as a bouncy ball:

• Calculate sum of digit squares
• The ball bounces to that new number
• Does it land on 1? HAPPY!
• Does it bounce forever in a loop? SAD!

Example: Is 19 Happy?

19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1 ✓ HAPPY!

Example: Is 2 Happy?

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4...

It loops! NOT happy.

The Code

function isHappy(n) {
  function getNext(num) {
    let sum = 0;
    while (num > 0) {
      let digit = num % 10;
      sum += digit * digit;
      num = Math.floor(num / 10);
    }
    return sum;
  }

  let slow = n;
  let fast = getNext(n);

  while (fast !== 1 && slow !== fast) {
    slow = getNext(slow);
    fast = getNext(getNext(fast));
  }

  return fast === 1;
}

Why Fast & Slow?

The sequence of digit-square-sums is like a linked list:

• Each number points to its sum of digit squares
• If it loops (not reaching 1), fast and slow will meet
• If it reaches 1, fast gets there first!

Problem 3: Find the Duplicate Number

The Challenge

Array of n+1 integers where each is between 1 and n. Find the duplicate.

Rules:

• Don’t modify the array
• Use only O(1) extra space

The Story

Imagine a treasure map with arrows. Each position tells you where to go next. If there’s a duplicate, two arrows point to the same spot - creating a LOOP!

How to See It

Array: [1, 3, 4, 2, 2]

Think of index → value as arrows:

Index 0 → Value 1 → Index 1
Index 1 → Value 3 → Index 3
Index 3 → Value 2 → Index 2
Index 2 → Value 4 → Index 4
Index 4 → Value 2 → Index 2 (LOOP!)

graph LR
    I0[0] -->|1| I1[1]
    I1 -->|3| I3[3]
    I3 -->|2| I2[2]
    I2 -->|4| I4[4]
    I4 -->|2| I2

The duplicate (2) is where the cycle starts!

The Code

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

  // Find meeting point in cycle
  do {
    slow = nums[slow];
    fast = nums[nums[fast]];
  } while (slow !== fast);

  // Find cycle entrance (duplicate)
  slow = nums[0];
  while (slow !== fast) {
    slow = nums[slow];
    fast = nums[fast];
  }

  return slow;
}

Step by Step with [1, 3, 4, 2, 2]

Phase 1: Find Meeting Point

Start: slow = 1, fast = 1
Step 1: slow = 3, fast = 2
Step 2: slow = 2, fast = 2 ← They meet!

Phase 2: Find Entrance

Reset: slow = 1, fast = 2
Step 1: slow = 3, fast = 4
Step 2: slow = 2, fast = 2 ← Meet at 2!

The duplicate is 2!

The Universal Pattern

All three problems share ONE idea:

The Recipe

// Phase 1: Detect cycle (find meeting point)
while (fast && fast.next) {
  slow = getNext(slow);
  fast = getNext(getNext(fast));
  if (slow === fast) break;
}

// Phase 2: Find cycle start
slow = start;
while (slow !== fast) {
  slow = getNext(slow);
  fast = getNext(fast);
}

Quick Memory Tips

Remember “The Race”:

• 🐢 Slow = 1 step
• 🐇 Fast = 2 steps
• 🔄 Loop = They meet
• 🏁 End = Fast finishes

Remember “Two Phases”:

1. Find Meeting - Different speeds
2. Find Entrance - Same speed from head and meeting point

When to Use Fast & Slow

Use this technique when you need to:

• Detect if a cycle exists
• Find where a cycle begins
• Find the middle of a linked list
• Detect patterns in number sequences

Key Insight: If any process has a finite set of states, it MUST eventually repeat. Fast & slow pointers help you find that repetition!

The tortoise and hare always meet. That’s not just a fable - it’s an algorithm!