Cycle Detector in Node Sequences — Problem Statement & Solution Guide

Two PointersHardFloyd's Cycle Detection

TimeO(n)

SpaceO(1)

Problem Description

You are provided with an array of integers representing a linked structure where each element at index i points to the next node via the value at that index. Specifically, the next node for index i is determined by the value nums[i]. The traversal starts at index 0. A cycle exists if the traversal eventually revisits an index that has already been visited. Your task is to determine whether such a cycle is present in the sequence defined by this pointer mapping.

The input is a single array of integers, nums, where each element represents the index of the next node in the sequence. The output should be a boolean value: true if a cycle is detected, and false otherwise. Note that the values in the array are guaranteed to be valid indices within the bounds of the array, ensuring the traversal remains within the defined structure.

To solve this efficiently, consider using a two-pointer technique to detect cycles without using additional memory for tracking visited nodes. This approach leverages the relative speeds of two pointers to determine if they ever meet, which would indicate the presence of a cycle.

DSA Pattern Breakdown

"Cycle Detector in Node Sequences"

hard

WHY DOES IT MATTER?

Detecting cycles with constant extra memory is a cornerstone of many system‑level problems, from detecting infinite redirects in web crawlers to ensuring termination in state machines. Mastery of the two‑pointer pattern demonstrates an ability to reason about pointer dynamics and space‑optimal designs, a skill highly prized in performance‑critical codebases.

OPTIMIZATION CHALLENGE

The key insight is to let two traversals run at different speeds so that the faster one inevitably catches up within the confined cycle space. This eliminates the need for external bookkeeping and leverages the deterministic nature of a functional graph.

REAL-WORLD CONNECTION

Consider a distributed token ring where each node forwards a token to its successor. If a node mistakenly forwards to an earlier node, the token loops forever, analogous to a cycle in our index array. Detecting such loops quickly prevents deadlock and resource exhaustion in networking protocols.

When coding under interview pressure, first write the simple loop that moves both pointers, then immediately add the bound checks. If the fast pointer reaches an invalid index, return false; otherwise, continue until the pointers meet.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to detecting a cycle in a functional graph where each index points to exactly one other index (or possibly itself). A naive linear scan with a visited set works but consumes O(n) extra memory, which becomes prohibitive for very large inputs. The optimal solution leverages the two‑pointer technique, famously known as Floyd’s Tortoise and Hare algorithm, which moves two pointers at different speeds through the sequence. If a cycle exists, the fast pointer will eventually lap the slow pointer, guaranteeing detection without auxiliary storage. This approach exploits the pigeonhole principle: with n+1 steps in a space of n indices, some index must repeat, and the differing speeds ensure that repetition is observed in linear time.

Why the naive approach fails on large inputs is twofold: first, the additional hash set or boolean array inflates memory usage, potentially exceeding limits for constraints up to 10^7 or more; second, the constant‑time overhead of hash operations can degrade performance. The two‑pointer paradigm sidesteps both issues by reusing the input indices as the traversal state, achieving O(1) auxiliary space while preserving O(n) time. Moreover, the algorithm can be extended to locate the entry point of the cycle by resetting one pointer to the start after detection and moving both at equal speed, a property often asked in follow‑up interview questions.

Interview Questions on This Problem

Q1How does Floyd’s Tortoise and Hare algorithm guarantee detection of a cycle in O(n) time and O(1) space?

The algorithm advances a slow pointer by one step and a fast pointer by two steps. In a cycle, the distance between them decreases by one each iteration modulo the cycle length, so they must meet within at most the cycle length steps. Since each pointer moves at most 2n steps overall, the time is linear, and only two pointers are stored, giving constant extra space.

Q2After detecting a cycle, how can you find the index where the cycle begins in the same O(n) time and O(1) space?

Once the slow and fast pointers meet, reset one pointer to the start (index 0) while keeping the other at the meeting point. Then move both pointers one step at a time; they will converge at the cycle’s entry point because they travel equal distances from the start and from the meeting point to the entry.

Q3What edge cases must you handle when the array may contain self‑loops or values that point outside the array bounds?

A self‑loop (nums[i] == i) is a valid cycle of length one and should be reported as true. If any value points outside the valid index range, the traversal terminates without a cycle, so the algorithm must check bounds before each move to avoid runtime errors.

Examples

Example 1

Input

nums = [1, 2, 3, 0]

Output

true

Explanation: Start at index 0. The next index is nums[0] = 1. From index 1, the next index is nums[1] = 2. From index 2, the next index is nums[2] = 3. From index 3, the next index is nums[3] = 0. Since we return to index 0, a cycle is detected. Output: true.

Example 2

Input

nums = [1, 2, 3, 4, 5]

Output

false

Explanation: Start at index 0. The next index is nums[0] = 1. From index 1, the next index is nums[1] = 2. From index 2, the next index is nums[2] = 3. From index 3, the next index is nums[3] = 4. From index 4, the next index is nums[4] = 5. However, index 5 is out of bounds for an array of length 5, so no cycle is formed. Output: false.

Example 3

Input

nums = [2, 0, 1]

Output

true

Explanation: Start at index 0. The next index is nums[0] = 2. From index 2, the next index is nums[2] = 1. From index 1, the next index is nums[1] = 0. Since we return to index 0, a cycle is detected. Output: true.

Example 4

Input

nums = [0, 1, 2, 3]

Output

true

Explanation: Start at index 0. The next index is nums[0] = 0. Since we immediately return to index 0, a cycle is detected. Output: true.

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] < nums.length
The array is guaranteed to be a valid pointer mapping where each element points to a valid index within the array.

Optimal Approach & Strategy

Apply Floyd’s Tortoise and Hare two‑pointer technique: move one pointer one step and the other two steps; if they meet, a cycle is present, otherwise termination occurs when a pointer goes out of bounds. This achieves O(1) auxiliary space.

Brute Force Approach

Traverse from index 0, storing each visited index in a hash set; if you encounter an index already in the set, a cycle exists. This uses O(n) extra space.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var hasCycle = function(nums) {
    const n = nums.length;
    if (n === 0) return false;
    
    let slow = 0;
    let fast = 0;
    
    while (true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        
        if (slow === fast) {
            return true;
        }
        
        if (slow < 0 || slow >= n || fast < 0 || fast >= n) {
            return false;
        }
    }
};

class Solution {
public:
    bool hasCycle(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return false;
        
        int slow = 0;
        int fast = 0;
        
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            
            if (slow == fast) {
                return true;
            }
            
            if (slow < 0 || slow >= n || fast < 0 || fast >= n) {
                return false;
            }
        }
    }
};

class Solution {
    public boolean hasCycle(int[] nums) {
        int n = nums.length;
        if (n == 0) return false;
        
        int slow = 0;
        int fast = 0;
        
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            
            if (slow == fast) {
                return true;
            }
            
            if (slow < 0 || slow >= n || fast < 0 || fast >= n) {
                return false;
            }
        }
    }
}

class Solution:
    def hasCycle(self, nums: List[int]) -> bool:
        n = len(nums)
        if n == 0:
            return False
        
        slow = 0
        fast = 0
        
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            
            if slow == fast:
                return True
            
            if slow < 0 or slow >= n or fast < 0 or fast >= n:
                return False

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var hasCycle = function(nums) {
    const n = nums.length;
    if (n === 0) return false;
    
    let slow = 0;
    let fast = 0;
    
    while (true) {
        slow = nums[slow];
        fast = nums[nums[fast]];
        
        if (slow === fast) {
            return true;
        }
        
        if (slow < 0 || slow >= n || fast < 0 || fast >= n) {
            return false;
        }
    }
};

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Cycle Detector in Node Sequences Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Two Pointers

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Cycle Detector in Node Sequences — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor