Detecting Cycles & Repeats: Fast & Slow Pointer Pattern

If you’ve ever watched two runners on a track, one sprinting and the other jogging, you know that sometimes the faster runner will eventually catch up to the slower one. This is exactly the intuition behind the fast & slow pointer pattern, used to detect cycles or repeated elements in arrays and linked structures efficiently.

Pattern Definition

The Fast & Slow Pointer Pattern involves two pointers moving at different speeds through a sequence. Typically, the fast pointer moves twice as fast as the slow pointer, and their meeting point indicates a cycle or repetition.

Think of it as two cars driving on a circular track: the faster car eventually laps the slower one. The moment they meet tells you something important about the track or the loop.

Problem Example: Find the Duplicate Number in Array

Sample Input: [3, 1, 3, 4, 2]

Goal: Find the number that appears twice without modifying the array or using extra space.

Real-Life Analogy: Imagine a conveyor belt in a factory with packages. One package repeats itself due to a misrouting. You want to detect the repeated package without scanning every slot multiple times.

Flow (Step-by-Step)

Start
  |
  v
Initialize:
  slow = nums[0] (slow runner)
  fast = nums[nums[0]] (fast runner)
  |
  v
Move:
  - slow moves 1 step: slow = nums[slow]
  - fast moves 2 steps: fast = nums[nums[fast]]
  |
  v
Check:
  - If slow == fast -> meeting point found
  - Else -> repeat moving pointers
  |
  v
Reset fast to start (fast = 0)
  |
  v
Move both 1 step at a time until slow == fast
  |
  v
Duplicate number found = slow

Kotlin Solution

fun findDuplicate(nums: IntArray): Int {
    var slow = nums[0]
    var fast = nums[nums[0]]

    while (slow != fast) {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }

    fast = 0
    while (slow != fast) {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

fun main() {
    val nums = intArrayOf(3, 1, 3, 4, 2)
    println(findDuplicate(nums)) // Output: 3
}

Time & Space Complexity

Time Complexity: O(n) Each pointer moves linearly. Even though the fast pointer moves twice as fast, it will meet the slow pointer within a single pass around the cycle.

Space Complexity: O(1) No extra storage is needed beyond the two pointers, making it space-efficient.

Real-Time Use Cases

1. Network Packet Loops: Detect repeated routing or infinite loops.

2. User Behavior Tracking: Identify repeating user actions for fraud detection.

3. Linked Lists & Memory Checks: Detect cycles in linked data.

4. Games & Animations: Detect collisions or overlaps on circular paths.

5. Event Scheduling: Detect repeated states in recurring sensor signals.

Conclusion

The fast & slow pointer pattern is a powerful, efficient tool for detecting cycles or duplicates without extra memory. It leverages speed differences to pinpoint repetitions in linear time.

Next Pattern: Expanding Around Center

Once you’ve mastered converging and racing pointers, the next trick is Expanding Around Center. Imagine checking for palindromes in a string: start from the middle and expand outward, capturing symmetric patterns. This technique is perfect for problems like longest palindromic substring or mirror patterns in arrays, and it also builds upon the two-pointer intuition.