Fast & Slow Pointers — A Pattern for Technical Problems

Published in

Strategio

4 min readOct 31, 2022

Hearing the phrase “technical interview” makes my heart beat a little faster. However, I’m on the quest to conquer my fear of technical interviews. To do this, I’m studying patterns for solving technical problems. Lately, I’ve been learning about Fast & Slow Pointers, and I figured that sharing this knowledge might be beneficial to other hopeful interviewees. So here’s a rundown of what I’ve learned about Fast & Slow Pointers!

Explanation

(Before diving into an explanation of Fast & Slow Pointers, it might be helpful to have an understanding of the Two Pointers pattern as well as linked list data structures.)

In the Fast & Slow Pointers technique, two pointers start at the same position and iterate through an array (or linked list) at different speeds. This is useful for finding cycles in linked lists. Picture two runners, one who is fast, and one who is slow. Both run around the same circular track, beginning from the same starting line. After starting, the fast runner quickly outpaces the slow runner. However, both runners will meet again when the fast runner loops back and comes up behind the slow runner. If you’ve seen Captain America: Winter Soldier, you might hear Steve Rogers saying, “On your left.”

When to Use This Pattern

This pattern is useful when dealing with problems which involve a cycle in a linked list. Here are a few problems that could be solved using Fast & Slow Pointers:

Using this Pattern: 141. Linked List Cycle (LeetCode)

Linked List Cycle is a simple but commonly asked interview question that I’ve sourced from LeetCode to demonstrate how Fast and Slow Pointers can be used to solve a problem. I’ll be coding my solutions in Java.

The following problem description can be found on LeetCode.

Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Solving with Brute Force:

A brute force solving method might use a HashSet. You could add each node to the set, checking each time if that node already exists in the set using the contains() method. If contains() returns false, that means the node has already been visited, and there is a cycle in the list. If every node has been visited, and contains() has never returned false, then there is no cycle in the list.

public class Solution {
    public boolean hasCycle(ListNode head) {
        
        HashSet<ListNode> set = new HashSet<ListNode>();
        
        while (head != null) {
            if (set.contains(head)) return true;
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

Time complexity: O(n) — The loop is traversed once.

Space complexity: O(n) —Storing items in the HashSet requires n space.

Solving with Fast and Slow Pointers:

If you recall my explanation of the Fast & Slow pattern, the fast runner outpaced the slow runner only to come up behind the slow runner again after finishing a loop. Therefore, you might see how the Fast & Slow Pointers algorithm can be applied to solve this problem. If there is a cycle, the fast and slow pointers will meet again after the fast pointer has iterated through the cycle. On the other hand, if there is no cycle, the pointers will not meet again.

public class Solution {
    public boolean hasCycle(ListNode head) {
                if(head == null || head.next == null) return false;
        
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        
        return false;
    }
}

Time complexity: O(n) — The loop is traversed once.

Space complexity: O(1) — No space is used.

Both solutions have a time complexity of O(n), but the Fast & Slow Pointers method uses no memory, so it’s a more optimized solution.

And that’s a quick introduction to Fast & Slow Pointers! I hope this explanation can be helpful to someone. I’m continuously learning about data structures & algorithms, so if you think I missed anything, let me know in the comments! 💭