Fast & Slow Pointers

Master the art of cycle detection and linked list manipulation using fast and slow pointers

Fast & Slow Pointers Pattern

The Fast & Slow pointers technique, also known as Floyd’s Tortoise and Hare algorithm or the two-pointer technique, is a pointer algorithm that uses two pointers moving through a sequence at different speeds. This pattern is particularly useful for:

  • Cycle detection
  • Finding middle elements
  • Finding list lengths
  • Determining sequence periodicity

Understanding Fast & Slow Pointers

The Fast & Slow pointer technique is like having two runners on a track - one running twice as fast as the other. This simple idea leads to powerful solutions for many problems.

Why Use Two Different Speeds?

  1. Cycle Detection: If there’s a cycle, the fast runner will eventually catch up to the slow runner. Think of it like running on a circular track - a faster runner will eventually lap the slower runner.

  2. Finding Middle: By the time the fast runner reaches the end, the slow runner will be halfway through. This is because the fast runner covers twice the distance in the same time.

  3. Distance Relationships: The relative speeds create useful mathematical relationships that help solve complex problems.

Real-World Analogies

  1. Race Track Analogy

    Think of a circular race track:
- Slow runner: jogging pace
- Fast runner: sprinting pace (2x speed)

Two scenarios:
1. Circular track (has cycle):
   - Runners will meet eventually
   - Like linked list cycle detection

2. Straight track (no cycle):
   - Fast runner reaches end
   - Slow runner at middle
   - Like finding middle element

  2. Clock Hands Analogy

    Similar to hour and minute hands:
- Hour hand (slow pointer)
- Minute hand (fast pointer)
- They meet at regular intervals
- Predictable meeting points

Core Concepts

  1. Movement Patterns

    Fast pointer moves twice as fast as slow pointer:

Initial:  1 → 2 → 3 → 4 → 5 → 6
         s,f

Step 1:   1 → 2 → 3 → 4 → 5 → 6
             s   f

Step 2:   1 → 2 → 3 → 4 → 5 → 6
                 s       f

  2. Cycle Detection

    def hasCycle(head: ListNode) -> bool:
    """
    Floyd's Cycle Detection Algorithm
    
    How it works:
    1. If there's a cycle, fast pointer will eventually catch up
    2. If no cycle, fast pointer reaches end
    
    Example:
    1 → 2 → 3 → 4 → 5
            ↑       ↓
            7 ← 6 ←┘
    
    Steps:
    1. slow=1, fast=1
    2. slow=2, fast=3
    3. slow=3, fast=5
    4. slow=4, fast=7
    5. slow=5, fast=2
    6. slow=6, fast=4
    7. slow=7, fast=6
    8. slow=3, fast=3 (meet!)
    """
    if not head or not head.next:
        return False
        
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
            
    return False

  3. Finding Cycle Start

    def detectCycle(head: ListNode) -> ListNode:
    """
    Floyd's Cycle Finding Algorithm
    
    Mathematical proof:
    Let's say:
    - Distance from head to cycle start = x
    - Distance from cycle start to meeting point = y
    - Remaining cycle length = z
    
    When they meet:
    Slow pointer traveled: x + y
    Fast pointer traveled: x + y + n(y + z) where n is number of cycles
    
    Since fast moves 2x speed:
    2(x + y) = x + y + n(y + z)
    x + y = n(y + z)
    x = n(y + z) - y
    x = (n-1)(y + z) + z
    
    This means: Moving x steps from head and meeting point reaches cycle start!
    """
    if not head or not head.next:
        return None
        
    # Find meeting point
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None
        
    # Find cycle start
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
        
    return slow

Common Applications

  1. Finding Middle Element

    def findMiddle(head: ListNode) -> ListNode:
    """
    Fast pointer moves twice, so when it reaches end,
    slow pointer is at middle.
    
    Example: 1 → 2 → 3 → 4 → 5
    
    Steps:
    1. s=1, f=1
    2. s=2, f=3
    3. s=3, f=5
    4. f reaches end, s at middle (3)
    """
    if not head or not head.next:
        return head
        
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
        
    return slow

  2. Finding List Length

    def findLength(head: ListNode) -> int:
    """
    Using cycle detection to find length.
    
    For cyclic lists:
    1. Find meeting point
    2. Count steps to complete one cycle
    
    For linear lists:
    Fast pointer reaches end, count slow pointer steps
    """
    if not head:
        return 0
        
    slow = fast = head
    length = 0
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        length += 1
        
        if slow == fast:  # Cycle detected
            cycle_length = 1
            slow = slow.next
            while slow != fast:
                cycle_length += 1
                slow = slow.next
            return cycle_length
            
    return length * 2 if fast else length * 2 - 1

Advanced Applications

  1. Happy Number Detection

    def isHappy(n: int) -> bool:
    """
    A number is happy if the sum of squares of its digits
    eventually equals 1.
    
    Example: 19
    1² + 9² = 82
    8² + 2² = 68
    6² + 8² = 100
    1² + 0² + 0² = 1 (Happy!)
    
    Uses cycle detection:
    - If sequence reaches 1, number is happy
    - If sequence cycles, number is not happy
    """
    def get_next(num):
        total = 0
        while num > 0:
            num, digit = divmod(num, 10)
            total += digit ** 2
        return total
        
    slow = fast = n
    while True:
        slow = get_next(slow)
        fast = get_next(get_next(fast))
        if fast == 1:
            return True
        if slow == fast:
            return False

  2. Palindrome Linked List

    def isPalindrome(head: ListNode) -> bool:
    """
    Uses fast/slow to find middle, then reverses second half
    
    Example: 1 → 2 → 2 → 1
    
    Steps:
    1. Find middle using fast/slow
    2. Reverse second half
    3. Compare first and second half
    """
    if not head or not head.next:
        return True
        
    # Find middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
        
    # Reverse second half
    second = slow.next
    prev = None
    while second:
        next_node = second.next
        second.next = prev
        prev = second
        second = next_node
        
    # Compare halves
    first = head
    second = prev
    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next
        
    return True

Edge Cases and Optimization

  1. Empty or Single Node

    # Always check for empty or single node
if not head or not head.next:
    return head  # or appropriate value

  2. Even vs Odd Length

    # For finding middle:
# Even length: first of middle two
# Odd length: middle element
while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

  3. Memory Optimization

    # In-place reversal for palindrome check
# Space: O(1) vs O(n) for storing values
def reverse(head):
    prev = None
    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node
    return prev

Practice Problems

  1. Basic

    • Linked List Cycle
    • Middle of Linked List
    • Happy Number
    • Palindrome Linked List

  2. Intermediate

    • Cycle Length
    • Start of Cycle
    • Reorder List
    • Intersection Point

  3. Advanced

    • Circular Array Loop
    • Find Duplicate Number
    • Split Circular Linked List
    • Clone Linked List with Random Pointer

Understanding Time Complexity

  1. Why O(n)? Even though we have two pointers:

    • Fast pointer moves at 2x speed
    • Total distance covered is still proportional to n
    • No nested loops in basic implementation

  2. Space Complexity Benefits Most Fast & Slow pointer solutions are O(1) space because:

    • Only need two pointers
    • No extra data structures
    • In-place modifications

Common Mistakes to Avoid

  1. Null Pointer Errors

    # Wrong:
while fast.next.next:  # Might throw error
    
# Correct:
while fast and fast.next:  # Safe null checking

  2. Off-by-One Errors

    # Finding middle in even-length lists:
# Be clear which middle element you want

1 → 2 → 3 → 4
    ↑   ↑
first second
middle middle

  3. Infinite Loops

    # Wrong:
while slow != fast:  # Might never meet
    slow = slow.next
    fast = fast.next.next
    
# Correct:
while fast and fast.next:  # Has exit condition

Interview Tips

  1. Problem Analysis

    • Explain why Fast & Slow pointers are suitable
    • Discuss alternatives and trade-offs
    • Mention space/time complexity benefits

  2. Solution Communication

    • Draw the pointer movements
    • Explain the mathematical reasoning
    • Discuss edge cases proactively
    • Mention potential optimizations

Remember: The key to mastering Fast & Slow pointers is to:

  1. Understand pointer movement patterns
  2. Handle edge cases carefully
  3. Consider memory optimization
  4. Practice with varied problems
  5. Understand the mathematical principles