Cycle Detection in Arrays

Welcome to the final lesson in our module on advanced linked list patterns. We've journeyed through list reversal, finding the middle node, detecting cycles, and even identifying a cycle's starting point. Most recently, you saw how to combine several of these patterns to efficiently check if a linked list is a palindrome.

Today, we're going to take the fast and slow pointer pattern one step further. You'll learn how this powerful technique isn't confined to linked lists alone. We will explore how to apply the very same cycle detection logic to solve a seemingly unrelated problem in an array. This lesson is all about pattern generalization—a crucial skill in advanced problem-solving, where you learn to see the underlying structure of a problem, even when it's disguised.

Our case study will be the classic "Find the Duplicate Number" problem. By the end of this lesson, you will be able to map this array problem to a conceptual linked list, identify the cycle created by the duplicate, and apply Floyd's algorithm to find it.

The Problem: Finding a Duplicate in a Constrained Array

Imagine you are given an array nums containing n + 1 integers, where every integer is in the range [1, n] inclusive. Because there are n + 1 numbers but only n possible values, the Pigeonhole Principle guarantees that at least one number must be repeated. The problem asks you to find this single duplicate number.

Now, here are the critical constraints that make this problem interesting:

1. You must not modify the input array.
2. You must use only constant, O(1), extra space.

These constraints immediately rule out common approaches. You can't use a hash set to track seen numbers (violates O(1) space), and you can't sort the array to find adjacent duplicates (violates the no-modification rule). This is where a more creative approach is needed.

The Insight: An Array as a Conceptual Linked List

The key to solving this problem is to stop seeing the array as just a static collection of numbers and start seeing it as a set of pointers defining a path. Let's treat each value in the array as a "pointer" to the next index.

If we are at an index i, the value nums[i] tells us which index to visit next. We can trace a sequence:
index_0 -> index_nums[0] -> index_nums[nums[0]] -> ...

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

• Start at index 0. The value is nums[0] = 1. Our next position is index 1.
• At index 1, the value is nums[1] = 3. Our next position is index 3.
• At index 3, the value is nums[3] = 2. Our next position is index 2.
• At index 2, the value is nums[2] = 4. Our next position is index 4.
• At index 4, the value is nums[4] = 2. Our next position is index 2.

The sequence of indices is 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> .... Notice that once we reach index 2, we are caught in a loop: 2 -> 4 -> 2 -> 4 -> .... We have found a cycle!

Why did a cycle form? It's because the value 2 is a duplicate. Both index 3 (nums[3]=2) and index 4 (nums[4]=2) point to the same destination: index 2. In linked list terminology, two different nodes are pointing to the same next node, which is the definition of a cycle's entry point.

Therefore, the duplicate number is the entry point of the cycle in this conceptual linked list.

This transformation allows us to reuse the powerful tool we already know: Floyd's Tortoise and Hare algorithm.

Applying Floyd's Cycle Detection Algorithm

We can now apply the two-phase algorithm you learned for linked lists directly to this array problem. The only change is how we move the pointers. Instead of pointer = pointer.next, we use pointer = nums[pointer].

1. Phase 1: Find the Intersection Point.

   • Initialize slow = nums[0] and fast = nums[nums[0]]. (We can also start both at index 0 and do the first move inside the loop).
   • In a loop, advance the pointers: slow = nums[slow] and fast = nums[nums[fast]].
   • They are guaranteed to meet somewhere inside the cycle.

2. Phase 2: Find the Cycle's Entry Point.

   • Once they meet, reset one pointer (let's call it slow2) back to the start of the "list" (index 0).
   • Keep the other pointer (slow) at the intersection point.
   • Advance both pointers one step at a time: slow = nums[slow] and slow2 = nums[slow2].
   • The point where they meet again is the entry point of the cycle, which is our duplicate number.

The following image illustrates the movement of the tortoise (slow) and hare (fast) pointers through an example array conceptualized as a linked sequence.

The mathematical proof that this second meeting point is the cycle's start is exactly the same as we discussed for linked lists. The "length" of the path segments is now counted in terms of array indices.

The following video from NeetCode provides an excellent walkthrough of this entire thought process, from recognizing the linked list structure to applying Floyd's algorithm.

For a more animated and concise explanation of the proof and the application, the "Inside code" video is also a great supplement.

To solidify your understanding, let's turn to some textual resources that break down the implementation and common pitfalls.

The NeetCode article provides another excellent and concise summary.

Conclusion

You have now seen how a pattern developed for one data structure (linked lists) can be brilliantly adapted to solve a problem in another (arrays). This is a testament to the power of abstraction in computer science. By recognizing the underlying "linked" nature of the array problem, you unlocked a highly efficient O(N) time and O(1) space solution that would otherwise be very difficult to discover.

Key Takeaways:

• An array where values are indices can be modeled as a linked list.
• In the "Find the Duplicate Number" problem, the specific constraints (n+1 elements in [1, n]) guarantee the existence of a cycle in this conceptual list.
• The duplicate number is the value corresponding to the entry point of the cycle.
• Floyd's Tortoise and Hare algorithm is the perfect tool to find this cycle entry point with O(1) space and without modifying the array.

This lesson concludes our deep dive into linked list patterns. You have built a solid toolkit for tackling a wide range of problems involving sequences and pointers.

In our next module, we will shift our focus to a new and fundamental non-linear data structure: trees. We'll start by exploring different ways to traverse them, beginning with level order traversal.