Cracking the Coding Interview: Part 4 – The Fast and Slow Pointer Technique

Cracking the Coding Interview: Part 4 – The Fast and Slow Pointer Technique

Before diving into this next technique, if you're preparing for coding interviews and want a comprehensive resource, be sure to explore Cracking the Coding Interview. It’s an essential book for anyone determined to land a job at top tech companies.

Overview of the Fast and Slow Pointer Technique

The Fast and Slow Pointer Technique (also known as Floyd’s Tortoise and Hare) is an elegant and effective pattern used to solve problems involving cycles in data structures like linked lists and arrays. The idea is to use two pointers that move at different speeds. Typically, one pointer (the "fast" one) moves two steps at a time, while the other pointer (the "slow" one) moves one step at a time. This allows you to efficiently detect cycles, find the middle of a linked list, and solve various other problems that involve patterns of repetition or middle points in a sequence.

When to Use Fast and Slow Pointers:

• The problem involves finding a cycle in a linked list or an array.
• You need to determine if a linked list has a cycle and locate the starting node of that cycle.
• You’re asked to find the middle element of a linked list in one pass.
• The problem deals with cyclic patterns or repeated sequences.

Fast and Slow Pointer Technique Applications

1. Detecting a Cycle in a Linked List

What it is: This is the classic problem solved by the fast and slow pointer method. If a linked list contains a cycle, the fast pointer will eventually meet the slow pointer, confirming the presence of a cycle.

Example Problem: Given a linked list, determine if it contains a cycle.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next  # Move slow by 1 step.
        fast = fast.next.next  # Move fast by 2 steps.

        if slow == fast:
            return True  # Cycle detected.

    return False  # No cycle detected.

Explanation:

• The slow pointer moves one step at a time, while the fast pointer moves two steps.
• If there is a cycle, the fast pointer will eventually catch up with the slow pointer, confirming the presence of a cycle.
• If the fast pointer reaches the end of the list, it means there is no cycle.

2. Finding the Start of a Cycle in a Linked List

What it is: Once a cycle is detected in a linked list, another common problem is to find the starting node of the cycle. This can be done by resetting one of the pointers to the head and moving both pointers one step at a time. They will meet at the start of the cycle.

Example Problem: Given a linked list with a cycle, find the node where the cycle begins.

def find_cycle_start(head):
    slow, fast = head, head
    cycle_exists = False

    # First, determine if a cycle exists.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            cycle_exists = True
            break

    if not cycle_exists:
        return None  # No cycle found.

    # Reset one pointer to the head and move both at the same speed.
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next

    return slow  # This is the start of the cycle.

Explanation:

• After detecting a cycle, reset one pointer to the head and move both pointers (slow and fast) one step at a time.
• The point where they meet is the starting node of the cycle.

3. Finding the Middle of a Linked List

What it is: The fast and slow pointer technique can also be used to find the middle element of a linked list in a single traversal.

Example Problem: Given a linked list, find the middle node.

def find_middle(head):
    slow, fast = head, head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow  # Slow will be at the middle when fast reaches the end.

Explanation:

• The fast pointer moves two steps at a time, while the slow pointer moves one step.
• When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Key Benefits of the Fast and Slow Pointer Technique

• Efficiency: This approach eliminates the need for multiple passes through a data structure. Instead, it handles most problems in just one pass, making it O(n) in time complexity.
• Simplicity: With just two pointers and a few conditions, it avoids the complexity of nested loops.
• Versatility: It can be applied to a variety of problems involving cycles, middle elements, or detecting repeated patterns in both linked lists and arrays.

Common Interview Questions Using Fast and Slow Pointers

1. Linked List Cycle Detection

Problem: Given a linked list, determine if it contains a cycle.
Solution: Use the fast and slow pointer approach to detect whether the two pointers meet.

2. Middle of the Linked List

Problem: Find the middle element of a singly linked list.
Solution: Move one pointer twice as fast as the other; the slower pointer will land in the middle by the time the faster one reaches the end.

3. Happy Number

Problem: A number is considered "happy" if, starting with any positive integer, replacing the number by the sum of the squares of its digits eventually leads to 1. If not, the sequence will enter a cycle. Detect if a number is a happy number.

Pattern: Use the fast and slow pointer approach to detect if the sequence enters a cycle.

def is_happy_number(n):
    def get_next(number):
        return sum(int(digit)**2 for digit in str(number))

    slow, fast = n, get_next(n)

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

    return fast == 1

Fast and Slow Pointer Hacks for Interviews

• Visualize with linked lists: This technique works best when visualized with linked lists, but it can apply to arrays and other sequences as well.
• Check cycle lengths carefully: In problems like finding the start of a cycle, it’s important to carefully track how long the cycle is before attempting to locate the starting point.
• Optimize for multiple traversals: When calculating positions like the middle of a list or detecting a cycle, think about how to minimize the number of traversals by using the fast and slow pointer method.

Conclusion

The Fast and Slow Pointer technique is a must-know tool in your interview toolbox. It’s perfect for problems involving cycles, middle elements, and repeated sequences. Mastering this pattern will enable you to solve common problems more efficiently, often reducing the time complexity from O(n²) to O(n).

In the next article, we’ll explore the Merge Intervals Pattern, another essential technique for coding interviews that will help you tackle scheduling and merging problems with ease.

Stay tuned for Part 5!