🏃♂️ The Tortoise and the Hare: Fast and Slow Pointers
A Racing Story That Solves Problems!
Imagine two friends on a circular running track. One friend is a speedy hare 🐰 who takes two steps at a time. The other is a slow tortoise 🐢 who takes one step at a time.
Here’s the magic question: If they start together and keep running, what happens?
- On a straight path: The hare zooms ahead and never looks back.
- On a circular path: The hare eventually catches up to the tortoise from behind! 🎯
This simple idea is called Fast and Slow Pointers (or Floyd’s Cycle Detection). It’s like having two detectives working at different speeds to find hidden patterns!
🎯 What Are Fast and Slow Pointers?
Think of it like two runners on a track:
| Pointer | Speed | Think of it as… |
|---|---|---|
| Slow | 1 step | 🐢 Tortoise walking |
| Fast | 2 steps | 🐰 Hare hopping |
The Big Idea:
- Start both at the same spot
- Move them at different speeds
- Watch where they meet (or don’t!)
// The basic pattern
ListNode slow = head;
ListNode fast = head;
while (fast != null &&
fast.next != null) {
slow = slow.next; // 🐢 1 step
fast = fast.next.next; // 🐰 2 steps
}
📍 Problem 1: Linked List Cycle II
The Story 📖
Imagine you’re in a maze. You walk and walk, and suddenly you realize: “Wait, I’ve been here before!”
That’s exactly what happens in a linked list with a cycle — you keep going in circles forever!
The Challenge: Find exactly WHERE the loop starts.
graph TD A[1] --> B[2] B --> C[3] C --> D[4] D --> E[5] E --> C style C fill:#ff6b6b,color:white
Node 3 is where the cycle starts!
How It Works 🔍
Phase 1: Find if there’s a cycle
- Send tortoise and hare running
- If hare catches tortoise → there’s a cycle!
Phase 2: Find where cycle starts
- Put one pointer back at the start
- Move BOTH at the same speed (1 step each)
- Where they meet = cycle start! 🎯
Why Does This Work? 🤔
It’s like math magic!
If tortoise traveled distance: D
Then hare traveled: 2D
The extra distance (D) = cycle length × K
When we reset one pointer to start and move both at same speed, they’re guaranteed to meet at the cycle entry!
The Code 💻
public ListNode detectCycle(ListNode head) {
// Phase 1: Detect cycle
ListNode slow = head;
ListNode fast = head;
while (fast != null &&
fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// 🎉 They met! Cycle exists
if (slow == fast) {
// Phase 2: Find entry
ListNode finder = head;
while (finder != slow) {
finder = finder.next;
slow = slow.next;
}
return finder;
}
}
return null; // No cycle
}
😊 Problem 2: Happy Number
The Story 📖
Some numbers are “happy” — they have a special secret!
Take any number. Add up the squares of its digits. Do it again. And again.
- Happy numbers eventually reach 1 🎉
- Sad numbers get stuck in a loop forever 😢
Example: Is 19 Happy?
19 → 1² + 9² = 1 + 81 = 82
82 → 8² + 2² = 64 + 4 = 68
68 → 6² + 8² = 36 + 64 = 100
100 → 1² + 0² + 0² = 1 ✨
19 is HAPPY! 🎉
Example: Is 2 Happy?
2 → 4 → 16 → 37 → 58 → 89 →
145 → 42 → 20 → 4 → ... (LOOP!)
2 is SAD 😢 (stuck in cycle)
The Connection 💡
Wait! This is just like finding a cycle!
- Happy number → reaches 1 (no cycle)
- Sad number → stuck in a loop (has a cycle!)
Use our tortoise and hare trick!
The Code 💻
public boolean isHappy(int n) {
int slow = n;
int fast = n;
do {
slow = sumOfSquares(slow);
fast = sumOfSquares(
sumOfSquares(fast)
);
} while (slow != fast);
return slow == 1;
}
private int sumOfSquares(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
🔢 Problem 3: Find the Duplicate Number
The Story 📖
Imagine a classroom with seats numbered 1 to N. Everyone has a ticket with a seat number on it. But wait — one student has a fake ticket with someone else’s seat number!
You need to find which seat number appears twice!
The Rules:
- Array has
n+1numbers - Numbers are from
1ton - Exactly ONE number repeats
Example
Array: [1, 3, 4, 2, 2]
↑ ↑
These two!
Answer: 2 (appears twice)
The Magic Trick 🎩
Think of the array as a linked list!
- Each number tells you “go to THIS position next”
- Since one number repeats → two arrows point to same place → CYCLE!
Index: 0 1 2 3 4
Value: [1, 3, 4, 2, 2]
Following the arrows:
0 → 1 → 3 → 2 → 4 → 2 → 4 → 2...
↑_______|
CYCLE!
The cycle entry point = the duplicate number!
The Code 💻
public int findDuplicate(int[] nums) {
// Phase 1: Find meeting point
int slow = nums[0];
int fast = nums[0];
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// Phase 2: Find cycle entry
slow = nums[0];
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
🧠 When to Use Fast & Slow Pointers?
| Situation | Why It Works |
|---|---|
| Cycle detection | Fast catches slow in a loop |
| Finding middle | When fast ends, slow is at middle |
| Finding cycle start | Math magic with distances |
| Detecting patterns | Repeated sequences = cycles! |
🚀 Key Takeaways
-
Fast moves 2x, Slow moves 1x — simple but powerful!
-
If there’s a cycle → they WILL meet
-
To find cycle start → reset one, move both at 1x
-
Think creatively — arrays can be linked lists!
-
Pattern: Loop or Converge → Try fast/slow!
🌟 Quick Reference
// PATTERN: Cycle Detection
slow = slow.next;
fast = fast.next.next;
// Meet? → Cycle exists!
// PATTERN: Find Cycle Start
// After meeting, reset one to start
// Move both at 1 step → meet at entry!
// PATTERN: Array as Linked List
// Value at index = next index
// Use: slow = nums[slow]
Remember: The tortoise always meets the hare in a circle! 🐢🐰