Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 20

Two-Pointer Patterns: Fast/Slow vs. Opposite-End

Recommended resources

Hello! Welcome back to our module on "Two-Pointers and Sliding Window."

In our previous lesson, you learned how to apply the opposite-ends two-pointer technique to solve problems on sorted arrays. We saw how initializing pointers at the start and end of an array and moving them inward can lead to highly efficient solutions. This strategy is powerful, but it's only one half of the two-pointer story.

Today, we'll focus on the second major pattern. Our goal is to differentiate between the fast/slow pointer and opposite-end pointer patterns. Understanding the fundamental differences between these two approaches is crucial for recognizing which one to apply when you encounter a new problem in competitive programming.

Let's get started by formally identifying these two patterns.

The Two Main Flavors of Two-Pointers

The "two-pointer" umbrella covers two primary strategies that differ in how the pointers are initialized and how they move.

To get a clear definition of these, please read a short section from the following article.

Cracking the Two Pointers Pattern

This article from Code by CodeBeast provides an excellent, concise breakdown of the two main variations of the two-pointer technique.

Please read the section titled 'Types of Two Pointer Patterns,' which appears after the 'Understanding the Basics' heading. Focus on the definitions for the 'Opposite Ends Pattern' and the 'Same Direction Pattern.' Stop when you reach the 'Pattern Breakdown and Recognition' section.

As you just read, the two main patterns are:

  1. Opposite-Ends Pattern: Pointers start at opposite ends and move toward each other.
  2. Same-Direction Pattern: Pointers start at the same end and move in the same direction, usually at different speeds. This is also commonly known as the fast and slow pointer pattern.

Let's quickly review the first pattern before diving into the second.

Pattern 1: Opposite-End Pointers (Recap)

You are already familiar with this pattern from our last lesson.

  • Initialization: One pointer at the beginning (left = 0), one at the end (right = len(arr) - 1).
  • Movement: The pointers move towards each other (left++, right--).
  • Core Idea: It's used on sorted data to find a pair of elements that satisfy a condition. The sorted nature allows you to make an intelligent decision about which pointer to move. If your current pair's sum is too small, you move the left pointer to get a larger value; if it's too big, you move the right pointer to get a smaller value.
Two-Pointer Technique: Finding Pair Sum in Sorted Array
This image illustrates the classic setup for the opposite-end pointer pattern. Pointers `left` and `right` start at the extremes of a sorted array to find a pair that sums to a target.

Classic problems for this pattern include Two Sum on a sorted array and checking if a string is a palindrome.

Pattern 2: Fast and Slow Pointers

This pattern, also called the "Tortoise and Hare" algorithm, works quite differently.

  • Initialization: Both pointers (slow and fast) usually start at the same position, typically the beginning of the data structure.
  • Movement: The pointers move in the same direction, but at different speeds. A common setup is slow moving one step at a time (slow = slow.next) while fast moves two steps (fast = fast.next.next).
  • Core Idea: The relative distance between the pointers is the key. This relative movement can help detect cycles, find middle elements, or solve other structural problems, particularly in linked lists.

The most famous application of this pattern is detecting a cycle in a linked list. If there's no cycle, the fast pointer will simply reach the end of the list first. But if there is a cycle, the fast pointer will enter it and eventually "lap" the slow pointer, meeting it at some point within the cycle.

Watch this short video segment for a demonstration.

How to Use the Two Pointer Technique

The video 'How to Use the Two Pointer Technique' by Team AlgoDaily provides a clear, animated explanation of using fast and slow pointers to detect a cycle in a linked list.

Please watch from 07:42 to 10:00. Observe how the different speeds of the two pointers guarantee they will meet if and only if a cycle exists.

The following image provides a static, step-by-step breakdown of the process you just watched.

Fast and Slow Pointer Movement in a Cyclic Linked List
This diagram shows the progression of fast and slow pointers in a linked list containing a cycle. The fast pointer moves two nodes at a time, while the slow pointer moves one. They are guaranteed to meet inside the cycle, confirming its existence.

This pattern is not limited to linked lists. It can also be cleverly applied to array problems. For example, in the "Find the Duplicate Number" problem, where you have n+1 integers in the range [1, n], you can think of the array as a linked list where index -> nums[index]. A duplicate number creates a cycle in this implicit graph, which the fast/slow pointer technique can detect.

Differentiating the Patterns: A Summary Table

This is the core of our lesson. Knowing which pattern to apply comes from recognizing the problem's structure. Here is a table to help you differentiate them.

Feature Opposite-End Pointers Fast/Slow Pointers
Pointer Setup One pointer at the start, one at the end. Both pointers at or near the start.
Pointer Movement Inward, towards each other. Same direction, but at different speeds.
Key Prerequisite Data is typically sorted (arrays, strings). Often used on linked lists or structures with sequential linking.
Problem Solved Finding a pair of elements that meets a condition. Detecting cycles, finding a middle point, or other structural properties.
Example Problem Two Sum on a sorted array, Valid Palindrome. Linked List Cycle, Find Middle of Linked List, Find Duplicate Number.
Test your understanding!

You are given two short problem descriptions. For each, decide whether the opposite-end or fast/slow pointer pattern is more appropriate, and briefly explain why.

  1. Given a sorted array of unique integers, find a pair that sums up to a target value k.
  2. Given the head of a singly linked list, determine if the list has a cycle.
Show answer

  1. Opposite-End Pointers. The problem involves a sorted array and asks to find a pair of elements. This is the classic setup for the opposite-end pattern. You can use the sum of the elements at the pointers to decide whether to move the left pointer right or the right pointer left.

  2. Fast/Slow Pointers. The problem involves a linked list and asks to detect a cycle. This is the textbook use case for the fast/slow pointer pattern. The different speeds of the pointers will cause them to meet if a cycle exists.

Conclusion

You have now learned about the two fundamental two-pointer patterns. Recognizing their distinct characteristics is a major step toward becoming proficient at solving array and list problems in competitive programming.

Key Takeaways:

  • The opposite-end pattern is your tool for sorted arrays when you're looking for pairs that satisfy a condition. The pointers converge based on comparing the current pair to a target.
  • The fast/slow pointer pattern is primarily for linked lists (or problems that can be modeled as such). It's used to find structural properties like cycles or middle points. The pointers move in the same direction at different speeds.

Up Next:
In the next lesson, we will explore the sliding window technique. This technique also uses two pointers that generally move in the same direction, but their logic is different from the fast/slow pattern. It's specifically designed to efficiently solve problems involving contiguous subarrays or substrings.