Overview

The Fast and Slow Pointers Pattern is based on the idea of using two pointers simultaneously to solve a problem more efficiently. The two pointers move through the data structure at different speeds, and this relative movement helps in finding a solution to various problems.

Understanding Fast & Slow Pointers Pattern

• It is a type of two pointers pattern where pointers move in the same direction.
• This approach also known as the Hare & Tortoise Algorithm.
• This approach is quite useful when dealing with cyclic linked lists or arrays.

Similar to the two pointers pattern, the fast and slow pointers pattern uses two pointers to traverse an iterable data structure at different speeds. It’s usually used to identify distinguishable features of directional data structures, such as a linked list or an array.

The pointers can be used to traverse the array or list in either direction, however, one moves faster than the other. Generally, the slow pointer moves forward by a factor of one, and the fast pointer moves by a factor of two in each step. However, the speed can be adjusted according to the problem statement.

Unlike the two pointers approach, which is concerned with data values, the fast and slow pointers approach is used to determine data structure traits using indices in arrays or node pointers in linked lists. The approach is commonly used to detect cycles in the given data structure, so it’s also known as Floyd’s cycle detection algorithm.

The key idea is that the pointers start at the same location, but they move forward at different speeds. If there is a cycle, the two are bound to meet at some point in the traversal. To understand the concept, think of two runners on a track. While they start from the same point, they have different running speeds. If the race track is a circle, the faster runner will overtake the slower one after completing a lap. On the other hand, if the track is straight, the faster runner will end the race before the slower one, hence never meeting on the track again. The fast and slow pointers pattern uses the same intuition.

Why Should I use it over the Two Pointer method

There are some cases where you shouldn’t use the Two Pointer approach such as in a singly linked list where you can’t move in a backwards direction. An example of when to use the Fast and Slow pattern is when you’re trying to determine if a linked list is a palindrome.

Example

let's consider an example of using the fast and slow pointers pattern to determine whether a given linked list contains a cycle.

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;

    ListNode *slow = head;
    ListNode *fast = head->next;

    while (fast && fast->next) {
        if (slow == fast) return true;
        slow = slow->next;
        fast = fast->next->next;
    }

    return false;
}

int main() {
    // Creating a cyclic linked list
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = head->next; // Creating a cycle

    // Checking if the linked list has a cycle
    std::cout << "Linked list has cycle? " << (hasCycle(head) ? "Yes" : "No") << std::endl;

    return 0;
}

Linked List: 1 -> 2 -> 3 -> 4
                   ^         |
                   |         |
                   +---------+

The fast pointer moves two steps at a time while the slow pointer moves one step at a time.

Initially:
slow = head (1)
fast = head->next (2)

First Iteration:
slow = 2
fast = 3

Second Iteration:
slow = 3
fast = 4

Third Iteration:
slow = 4
fast = 2

At this point, slow and fast pointers meet, indicating that the linked list has a cycle.