🐢🐰 The Tortoise and the Hare: Fast and Slow Pointers

Imagine two friends walking on a circular track. One walks slowly, one runs fast. What happens when they keep going around and around?

🌟 The Big Idea

Fast and Slow Pointers is like having two runners on a track:

• Slow Runner (Tortoise) 🐢 takes 1 step at a time
• Fast Runner (Hare) 🐰 takes 2 steps at a time

Why does this matter?

• If there’s a loop, they WILL meet!
• If there’s no loop, the fast one reaches the end first

graph TD
    A[Start Together] --> B[Slow: 1 step]
    A --> C[Fast: 2 steps]
    B --> D{Is there a cycle?}
    C --> D
    D -->|Yes| E[They WILL meet!]
    D -->|No| F[Fast reaches end]

🎯 Why Learn This?

Think about it like this:

Without this technique:

• You’d need extra memory to remember visited places
• You’d need complicated tracking systems

With Fast & Slow Pointers:

• Just two simple pointers
• No extra memory needed!
• Super elegant and fast

📚 Problem 1: Linked List Cycle II

The Story 📖

Imagine you’re walking through a maze of rooms. Each room has a door to the next room. But wait… some mazes are TRICKY! The last room might connect back to an earlier room, creating an endless loop!

Your Mission: Find WHERE the loop starts!

Visual Example

1 → 2 → 3 → 4 → 5
        ↑       ↓
        └───────┘

The cycle starts at node 3!

How It Works 🔍

Step 1: Detect the cycle

def detectCycle(head):
    slow = head
    fast = head

    # Move until they meet
    while fast and fast.next:
        slow = slow.next        # 1 step
        fast = fast.next.next   # 2 steps

        if slow == fast:
            # They met! Cycle exists!
            break

Step 2: Find the start

    # Reset one pointer to head
    slow = head

    # Move both at same speed
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # This is where cycle starts!

Why Does This Work? 🤔

Imagine the tortoise and hare on a track:

Distance to cycle start = a
Cycle length = c
Meeting point inside cycle = b

When they meet:
- Slow traveled: a + b
- Fast traveled: a + b + c

Since fast = 2 × slow:
2(a + b) = a + b + c
a = c - b

Translation: After they meet, if one starts from the beginning and both move at the same speed, they’ll meet at the cycle start! Magic! ✨

📚 Problem 2: Happy Number

The Story 📖

A number wants to be happy! To check if it’s happy:

1. Square each digit
2. Add them together
3. Repeat with the result

If you eventually reach 1, the number is HAPPY! 🎉 If you go in circles forever, it’s SAD. 😢

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

We reached 1! 🎉 19 is HAPPY!

Example: Is 2 Happy?

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

It loops back to 4! 😢 2 is NOT happy.

The Code 🐍

def isHappy(n):
    def get_next(number):
        total = 0
        while number > 0:
            digit = number % 10
            total += digit ** 2
            number //= 10
        return total

    slow = n
    fast = get_next(n)

    while fast != 1 and slow != fast:
        slow = get_next(slow)
        fast = get_next(get_next(fast))

    return fast == 1

Why Fast & Slow? 🐢🐰

The sequence of sums will either:

1. Reach 1 (happy!)
2. Enter a cycle (not happy)

Using two pointers:

• If they meet at 1 → Happy! ✅
• If they meet elsewhere → Sad cycle! ❌

📚 Problem 3: Find the Duplicate Number

The Story 📖

You have a bag with n+1 balls numbered from 1 to n. ONE number appears twice! Find it without:

• Sorting the array
• Using extra space

The Clever Insight 💡

Treat array indices like a linked list!

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

Think of it as:
- From index 0, go to index 1 (value = 1)
- From index 1, go to index 3 (value = 3)
- From index 3, go to index 2 (value = 2)
- From index 2, go to index 4 (value = 4)
- From index 4, go to index 2 (value = 2)

There's a cycle starting at index 2!
The duplicate is 2!

graph LR
    A[0] -->|1| B[1]
    B -->|3| C[3]
    C -->|2| D[2]
    D -->|4| E[4]
    E -->|2| D

The Code 🐍

def findDuplicate(nums):
    # Phase 1: Find intersection
    slow = nums[0]
    fast = nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    # Phase 2: Find cycle start
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow

Step-by-Step Walkthrough

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

Reset slow to start:

Answer: 2 ✅

🧠 Pattern Recognition

When to Use Fast & Slow Pointers?

Ask yourself:

1. 🔄 Does the problem involve cycles?
2. 🔗 Can I model it as a linked structure?
3. 💾 Do I need O(1) space?

If YES to any → Try Fast & Slow! 🚀

🎁 Key Takeaways

graph TD
    A[Fast & Slow Pointers] --> B[Detect Cycles]
    A --> C[Find Cycle Start]
    A --> D[O1 Space Complexity]
    B --> E[Linked List Cycle]
    B --> F[Happy Number]
    C --> G[Cycle Entry Point]
    C --> H[Find Duplicate]

Remember! 🌟

1. Two pointers, different speeds

   • Slow: 1 step
   • Fast: 2 steps

2. If there’s a cycle, they WILL meet

   • Math guarantees it!

3. Finding cycle start:

   • After meeting, reset one to start
   • Move both at same speed
   • They meet at the cycle start!

💪 You’ve Got This!

You now understand one of the most elegant techniques in programming! The Tortoise and Hare algorithm is:

• Simple to implement
• Powerful for cycle problems
• Memory efficient (O(1) space!)

Next time you see a problem involving cycles or duplicates, you’ll know exactly what to do! 🎉

“Like the tortoise who eventually catches up to the hare, persistence and the right technique will always find the answer!” 🐢🐰