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 1

Fast/Slow Pointers for Cycles and Duplicates

Recommended resources

Hello! Welcome to the first lesson in your journey to master LeetCode patterns for top tech interviews.

Today, we'll dive into our first major pattern from the "Core Array and String Patterns" module: the Fast/Slow Pointer technique. This powerful pattern, also known as the "Hare & Tortoise" algorithm, is a fantastic tool for solving a class of problems that seem tricky at first glance, especially those involving cycles or specific positions in a sequence. By the end of this lesson, you'll be able to apply this pattern to identify cycles and find duplicates in arrays, a common scenario in coding interviews.

1. The Core Idea: Hare and Tortoise

The Fast & Slow Pointer pattern uses two pointers that traverse a data structure at different speeds. A "slow" pointer moves one step at a time, while a "fast" pointer moves two steps at a time.

Floyd's Cycle Detection Illustration
This image, often used to explain Floyd's Cycle Detection algorithm, visualizes the core concept. A "slow" pointer (the tortoise) and a "fast" pointer (the hare) start at the same position and move through a sequence at different speeds.

This difference in speed is the key. If the data structure you are traversing has a cycle, the fast pointer will eventually lap the slow pointer and they will meet. If there is no cycle, the fast pointer will simply reach the end of the sequence first.

To build our intuition, let's first see how this works in its most classic application: detecting a cycle in a linked list.

Pattern 3: Fast & Slow pointers

This resource provides an excellent introduction to the Fast & Slow pointer pattern and explains why the two pointers are guaranteed to meet if a cycle exists.

Please read the section titled 'LinkedList Cycle (easy)'. Focus on the logical argument for why the pointers must eventually meet within a cycle. You can skim the code, as we'll be focusing on an array application next.

As you just read, the pointers are bound to meet. The following image breaks down this interaction step-by-step.

Fast/Slow Pointer Cycle Detection Visualization
This diagram shows the movement of slow and fast pointers through a linked list containing a cycle. In each step, the slow pointer advances one node while the fast pointer advances two. You can see them eventually colliding at node 5.

2. Applying the Pattern: Find the Duplicate Number

Now, let's apply this to an array problem. This is where the pattern recognition skill becomes crucial for interviews. Consider this classic problem:

You are given an array nums containing n + 1 integers where each integer is in the range [1, n] inclusive. There is only one repeated number in nums. Your task is to find this repeated number.

Constraints: You must solve the problem without modifying the array nums and using only constant extra space.

The constraints are what make this problem tricky. A hash set would violate O(1) space, and sorting would violate the "no modification" rule. This is a perfect setup for the Fast/Slow Pointer pattern, but how can an array have a "cycle"?

The key insight is to visualize the array as a linked list.

  • Each index i in the array can be seen as a "node".
  • The value at that index, nums[i], can be seen as the "next" pointer.

For example, if nums = [1, 3, 4, 2, 2]:

  • Index 0 "points" to index 1 (since nums[0] = 1).
  • Index 1 "points" to index 3 (since nums[1] = 3).
  • Index 3 "points" to index 2 (since nums[3] = 2).
  • Index 2 "points" to index 4 (since nums[2] = 4).
  • Index 4 "points" to index 2 (since nums[4] = 2).

The sequence of traversals is 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 ...
Notice that because nums[3] and nums[4] both equal 2, two "nodes" point to index 2. This creates a cycle! The repeated number is the entrance to this cycle.

To see this conceptual leap explained visually, the following video is excellent.

Find the Duplicate Number - Floyd's Cycle Detection - Leetcode 287 - Python

This video from NeetCode brilliantly explains how to model the array as a linked list. Understanding this transformation is the most important step to solving the problem.

Watch from 01:48 to 06:13. Focus on how the array values are treated as 'pointers' to indices, and why the duplicate number is guaranteed to be the starting point of a cycle in this model.

3. The Two-Phase Algorithm

Now that we've framed this as a cycle detection problem, we can use Floyd's "Tortoise and Hare" algorithm. It consists of two phases:

  1. Phase 1: Find an intersection point. Move a slow pointer one step at a time (slow = nums[slow]) and a fast pointer two steps at a time (fast = nums[nums[fast]]). They are guaranteed to meet somewhere inside the cycle.
  2. Phase 2: Find the cycle's entrance. Once they meet, reset one pointer (let's say slow) back to the starting position (slow = nums[0]). Keep the fast pointer at the intersection point. Now, move both pointers one step at a time. The point where they meet again is the entrance to the cycle, which is our duplicate number.

This two-phase approach is the heart of the algorithm.

Test your understanding!

Given the array nums = [1, 3, 4, 2, 2], let's trace the pointers. We'll start both pointers at index 0. However, to get the process started, we'll initialize slow = nums[0] and fast = nums[nums[0]].

Can you trace the values of slow and fast in each iteration until they meet in Phase 1?

Initial State:
slow = nums[0] = 1
fast = nums[nums[0]] = nums[1] = 3

Iteration 1:
slow = nums[slow] = nums[1] = ?
fast = nums[nums[fast]] = nums[nums[3]] = ?

...and so on. Where do they meet?

Show answer

Initial: slow = 1, fast = 3

Iteration 1:

  • slow = nums[1] = 3
  • fast = nums[nums[3]] = nums[2] = 4
    (State: slow = 3, fast = 4)

Iteration 2:

  • slow = nums[3] = 2
  • fast = nums[nums[4]] = nums[2] = 4
    (State: slow = 2, fast = 4)

Iteration 3:

  • slow = nums[2] = 4
  • fast = nums[nums[4]] = nums[2] = 4
    (State: slow = 4, fast = 4)

They meet at value 4!

Now, for Phase 2, we reset one pointer. Let's create a new pointer, slow2, and set it to nums[0]. We keep slow at the meeting point 4.

Phase 2 Start: slow = 4, slow2 = nums[0] = 1

Iteration 1:

  • slow = nums[4] = 2
  • slow2 = nums[1] = 3
    (State: slow = 2, slow2 = 3)

Iteration 2:

  • slow = nums[2] = 4
  • slow2 = nums[3] = 2
    (State: slow = 4, slow2 = 2)

Iteration 3:

  • slow = nums[4] = 2
  • slow2 = nums[2] = 4
    (State: slow = 2, slow2 = 4)

Wait, the logic in the video/articles seems simpler. Let's adjust slightly. The common implementation is to start slow and fast at nums[0], do the first step, then loop. A slightly different but equivalent approach is to start a second pointer from 0 (not nums[0]). Let's follow the standard implementation for clarity.

Let's re-trace with a cleaner standard implementation:

  • Pointers slow and fast start at index 0.

Phase 1
Initial: slow = 0, fast = 0

  1. slow = nums[0] = 1, fast = nums[nums[0]] = nums[1] = 3
  2. slow = nums[1] = 3, fast = nums[nums[3]] = nums[2] = 4
  3. slow = nums[3] = 2, fast = nums[nums[4]] = nums[2] = 4
  4. slow = nums[2] = 4, fast = nums[nums[4]] = nums[2] = 4
    -> They meet when both point to index 4. The values they hold are 4.

Phase 2

  • Reset slow to index 0.
  • Keep fast at index 4.
  • A new pointer slow2 will start at 0. fast stays where it is. Let's just call them p1 and p2.
  • p1 = 0, p2 = 4
  1. p1 = nums[0] = 1, p2 = nums[4] = 2
  2. p1 = nums[1] = 3, p2 = nums[2] = 4
  3. p1 = nums[3] = 2, p2 = nums[4] = 2
    -> They meet when both point to index 2. The value is 2. The duplicate is 2.

This re-trace shows a subtle but important detail in implementation. The core logic of the two phases remains the same.

4. Implementation in Code

Seeing the algorithm in code solidifies the concept. Since you work with Node.js, the following resource's TypeScript example will be very familiar.

LeetCode #287 — Find the Duplicate Number from Naive to Optimal Solution

This article provides a very clear code implementation and a step-by-step walkthrough of the example we just discussed. It's a great way to connect the abstract algorithm to concrete code.

Read the section 'Floyd’s Two Phase Algorithm'. Pay close attention to the 'Final Code' section and the 'Example Walkthrough' to see the pointers in action.

The logic you saw in the TypeScript code translates almost directly to JavaScript. The key is the do-while loop for Phase 1 (to ensure the pointers move at least once before checking for equality) and a while loop for Phase 2.

A common question is: why does Phase 2 work? While a deep mathematical proof is not essential for interviews, the intuition is that the distance from the start of the list to the cycle entrance is equal to the distance from the intersection point to the cycle entrance. This is why moving two pointers at the same speed from these two locations guarantees they meet at the cycle's start. If you're curious, the NeetCode video (LINK) explains this proof visually from 08:22 onwards.

Conclusion

Congratulations on completing your first lesson! You've learned a powerful and non-obvious pattern that is a favorite in technical interviews.

Key Takeaways:

  • The Fast & Slow Pointer pattern is highly effective for problems involving cycles in sequential data structures.
  • Creative problem-solving is key. We transformed an array problem into a linked list cycle problem by re-imagining indices as nodes and values as pointers.
  • Floyd's Cycle-Finding Algorithm is a two-phase process: first find any intersection point within the cycle, then use that point to find the cycle's entrance.

This pattern is not a one-trick pony. It can be adapted to other problems, such as finding the middle of a linked list or determining if a number's digits will eventually sum to 1 (Happy Number problem).

Preview of the Next Lesson:
We will continue with the Two Pointers theme but explore a different variation: using two pointers that move from opposite ends of an array towards each other. This is a fundamental pattern for solving a wide range of problems, including the famous 2Sum and 3Sum problems. See you then