Find Cycle in Array (Jump Game)

🎯

Find Cycle in Array (Jump Game)

mediumTWO_POINTERGoogleAmazon

Imagine a game where you jump through an array using the values as steps, and you want to know if you can get stuck in an infinite loop.

💡 This problem involves detecting cycles in sequences defined implicitly by array indices. Beginners often struggle because the 'next' element isn't given explicitly but must be computed, and cycles can be tricky to detect without extra space or clever pointers.

📋

Problem Statement

Given a circular array of integers where each element represents the number of steps to move forward (positive) or backward (negative), determine if there exists a cycle in the array. A cycle must be longer than 1 element and must be all in the same direction (all positive or all negative). Return true if such a cycle exists, otherwise false.

1 ≤ n ≤ 10^5-10^5 ≤ nums[i] ≤ 10^5nums[i] ≠ 0 for all i

💡

Example

Input"[2, -1, 1, 2, 2]"

Outputtrue

Starting at index 0, jump 2 steps to index 2, then jump 1 step to index 3, then jump 2 steps to index 0 again, forming a cycle.

Input"[-1, 2]"

Outputfalse

No cycle exists because the jumps change direction.

• Array with all positive numbers forming a cycle → true
• Array with all negative numbers forming a cycle → true
• Array with single element → false (cycle length must be > 1)
• Array where jumps lead to self-loop (cycle length 1) → false

⚠️

Common Mistakes

Not handling negative modulo correctly

Index out of bounds or incorrect next index calculation

✅ Add n to modulo result if negative to wrap around correctly

Counting self-loop (cycle length 1) as valid cycle

Incorrectly returns true for invalid cycles

✅ Check if next index equals current index and reject such cycles

Mixing directions in cycle detection

False positives or missed cycles

✅ Ensure all jumps in cycle have the same sign (direction)

Not marking visited nodes leading to repeated work

Inefficient code causing TLE

✅ Mark visited nodes (e.g., set to zero) to skip them in future iterations

Using extra space for visited sets in optimal approach

Increased space complexity and slower performance

✅ Use in-place marking and fast-slow pointers instead of extra sets

🧠

Brute Force (Simulation with Visited Set)

💡 This approach exists to build intuition by simulating jumps from each index and tracking visited indices to detect cycles. It is straightforward but inefficient, helping beginners understand the problem structure.

Intuition

Try starting from each index and simulate jumps until you either find a cycle or reach an index visited before without forming a valid cycle.

Algorithm

1. For each index in the array, start simulating jumps.
2. Keep track of visited indices in a set for the current start.
3. If you revisit an index in the current path, check if cycle length > 1 and direction is consistent.
4. If a valid cycle is found, return true; otherwise, continue.
5. If no cycles found after all starts, return false.

💡 The nested loops and visited sets make it hard to see efficiency, but it clearly shows how cycles form by direct simulation.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    for start in range(n):
        visited = set()
        current = start
        direction = nums[start] > 0
        while True:
            if nums[current] == 0:
                break
            if (nums[current] > 0) != direction:
                break
            if current in visited:
                next_index = (current + nums[current]) % n
                if next_index < 0:
                    next_index += n
                # Check cycle length > 1 (no self-loop)
                if next_index != current:
                    return True
                else:
                    break
            visited.add(current)
            next_index = (current + nums[current]) % n
            if next_index < 0:
                next_index += n
            if next_index == current:
                break
            current = next_index
    return False

# Example usage
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

for start in range(n):Try starting the simulation from every index to find any cycle.

visited = set()Track indices visited in the current simulation to detect cycles.

direction = nums[start] > 0Determine the direction of jumps to ensure cycle consistency.

if (nums[current] > 0) != direction:Break if direction changes, as cycles must be unidirectional.

if current in visited:If we revisit an index in the current path, a cycle might exist; check cycle length.

next_index = (current + nums[current]) % nCalculate next index with wrap-around using modulo.

if next_index < 0:Adjust for negative modulo results to keep index valid.

if next_index != current:Ensure cycle length > 1 by rejecting self-loops.

visited.add(current)Add current index to visited set to track path.

if next_index == current:Break if jump leads to self-loop, which is invalid cycle.

return FalseNo cycle found after checking all indices.

import java.util.*;
public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            Set<Integer> visited = new HashSet<>();
            int current = start;
            boolean direction = nums[start] > 0;
            while (true) {
                if (nums[current] == 0) break;
                if ((nums[current] > 0) != direction) break;
                if (visited.contains(current)) {
                    int next = (current + nums[current]) % n;
                    if (next < 0) next += n;
                    if (next != current) return true;
                    else break;
                }
                visited.add(current);
                int next = (current + nums[current]) % n;
                if (next < 0) next += n;
                if (next == current) break;
                current = next;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

for (int start = 0; start < n; start++) {Try starting simulation from each index to find cycles.

Set<Integer> visited = new HashSet<>();Track visited indices in current simulation to detect cycles.

boolean direction = nums[start] > 0;Determine jump direction to ensure cycle consistency.

if ((nums[current] > 0) != direction) break;Break if direction changes, invalidating cycle.

if (visited.contains(current)) {If current index revisited, check cycle length.

int next = (current + nums[current]) % n;Calculate next index with wrap-around.

if (next < 0) next += n;Adjust for negative modulo results to keep index valid.

if (next != current) return true;Return true if cycle length > 1 (no self-loop).

visited.add(current);Add current index to visited set to track path.

if (next == current) break;Break if jump leads to self-loop, invalid cycle.

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int start = 0; start < n; start++) {
            unordered_set<int> visited;
            int current = start;
            bool direction = nums[start] > 0;
            while (true) {
                if (nums[current] == 0) break;
                if ((nums[current] > 0) != direction) break;
                if (visited.count(current)) {
                    int next = (current + nums[current]) % n;
                    if (next < 0) next += n;
                    if (next != current) return true;
                    else break;
                }
                visited.insert(current);
                int next = (current + nums[current]) % n;
                if (next < 0) next += n;
                if (next == current) break;
                current = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Start simulation from each index to find cycles.

unordered_set<int> visited;Track visited indices in current simulation to detect cycles.

bool direction = nums[start] > 0;Determine jump direction for cycle consistency.

if ((nums[current] > 0) != direction) break;Break if direction changes, invalid cycle.

if (visited.count(current)) {If revisiting index, check cycle length.

int next = (current + nums[current]) % n;Calculate next index with wrap-around.

if (next < 0) next += n;Adjust negative modulo to valid index.

if (next != current) return true;Return true if cycle length > 1 (no self-loop).

visited.insert(current);Add current index to visited set to track path.

if (next == current) break;Break if jump leads to self-loop, invalid cycle.

function circularArrayLoop(nums) {
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        const visited = new Set();
        let current = start;
        const direction = nums[start] > 0;
        while (true) {
            if (nums[current] === 0) break;
            if ((nums[current] > 0) !== direction) break;
            if (visited.has(current)) {
                let next = (current + nums[current]) % n;
                if (next < 0) next += n;
                if (next !== current) return true;
                else break;
            }
            visited.add(current);
            let next = (current + nums[current]) % n;
            if (next < 0) next += n;
            if (next === current) break;
            current = next;
        }
    }
    return false;
}

// Example usage
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

for (let start = 0; start < n; start++) {Try starting simulation from each index to find cycles.

const visited = new Set();Track visited indices in current simulation to detect cycles.

const direction = nums[start] > 0;Determine jump direction for cycle consistency.

if ((nums[current] > 0) !== direction) break;Break if direction changes, invalid cycle.

if (visited.has(current)) {If revisiting index, check cycle length.

let next = (current + nums[current]) % n;Calculate next index with wrap-around.

if (next < 0) next += n;Adjust negative modulo to valid index.

if (next !== current) return true;Return true if cycle length > 1 (no self-loop).

visited.add(current);Add current index to visited set to track path.

if (next === current) break;Break if jump leads to self-loop, invalid cycle.

⏱

Complexity

TimeO(n^2)

SpaceO(n)

For each of the n indices, we simulate jumps which can take up to O(n) steps in worst case, leading to O(n^2) time. The visited set uses O(n) space.

💡 For n=1000, this means up to 1,000,000 operations, which is slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and cycle detection basics.

🧠

Fast and Slow Pointer (Floyd's Cycle Detection)

💡 This approach uses two pointers moving at different speeds to detect cycles efficiently without extra space, a classic technique for cycle detection in linked structures.

Intuition

Use a slow pointer moving one step and a fast pointer moving two steps. If they meet, a cycle exists. Check direction and cycle length constraints.

Algorithm

1. Iterate over each index as a potential start.
2. If the element is zero, skip since it was visited or invalid.
3. Initialize slow and fast pointers at start.
4. Move slow by one step and fast by two steps, checking direction consistency.
5. If slow meets fast, check cycle length > 1 and return true.
6. Mark all visited elements in the current path as zero to avoid reprocessing.
7. If no cycle found, return false.

💡 The marking step avoids revisiting processed paths, improving efficiency.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    def next_index(i):
        return (i + nums[i]) % n

    for i in range(n):
        if nums[i] == 0:
            continue
        slow, fast = i, i
        direction = nums[i] > 0
        while True:
            slow_next = next_index(slow)
            fast_next = next_index(fast)
            if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:
                break
            fast_next = next_index(fast_next)
            if (nums[fast_next] > 0) != direction:
                break
            slow, fast = slow_next, fast_next
            if slow == fast:
                if slow == next_index(slow):
                    break
                return True
        # Mark all nodes in the current path as 0
        marker = i
        while (nums[marker] != 0) and ((nums[marker] > 0) == direction):
            next_marker = next_index(marker)
            nums[marker] = 0
            marker = next_marker
    return False

# Example usage
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

def next_index(i):Helper to compute next index with wrap-around.

if nums[i] == 0:Skip indices already processed or invalid.

direction = nums[i] > 0Determine jump direction for cycle consistency.

slow_next = next_index(slow)Move slow pointer one step.

fast_next = next_index(fast)Move fast pointer one step first.

fast_next = next_index(fast_next)Move fast pointer second step.

if slow == fast:Pointers meet, possible cycle detected.

if slow == next_index(slow):Check for self-loop, invalid cycle.

nums[marker] = 0Mark visited indices to avoid reprocessing.

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            boolean direction = nums[i] > 0;
            while (true) {
                int slowNext = nextIndex(nums, slow);
                int fastNext = nextIndex(nums, fast);
                if ((nums[slowNext] > 0) != direction || (nums[fastNext] > 0) != direction) break;
                fastNext = nextIndex(nums, fastNext);
                if ((nums[fastNext] > 0) != direction) break;
                slow = slowNext;
                fast = fastNext;
                if (slow == fast) {
                    if (slow == nextIndex(nums, slow)) break;
                    return true;
                }
            }
            int marker = i;
            while (nums[marker] != 0 && (nums[marker] > 0) == direction) {
                int next = nextIndex(nums, marker);
                nums[marker] = 0;
                marker = next;
            }
        }
        return false;
    }

    private int nextIndex(int[] nums, int i) {
        int n = nums.length;
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

if (nums[i] == 0) continue;Skip indices already processed or invalid.

boolean direction = nums[i] > 0;Determine jump direction for cycle consistency.

int slowNext = nextIndex(nums, slow);Move slow pointer one step.

int fastNext = nextIndex(nums, fast);Move fast pointer one step first.

fastNext = nextIndex(nums, fastNext);Move fast pointer second step.

if (slow == fast) {Pointers meet, possible cycle detected.

if (slow == nextIndex(nums, slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int nextIndex(const vector<int>& nums, int i) {
        int n = nums.size();
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            bool direction = nums[i] > 0;
            while (true) {
                int slowNext = nextIndex(nums, slow);
                int fastNext = nextIndex(nums, fast);
                if ((nums[slowNext] > 0) != direction || (nums[fastNext] > 0) != direction) break;
                fastNext = nextIndex(nums, fastNext);
                if ((nums[fastNext] > 0) != direction) break;
                slow = slowNext;
                fast = fastNext;
                if (slow == fast) {
                    if (slow == nextIndex(nums, slow)) break;
                    return true;
                }
            }
            int marker = i;
            while (nums[marker] != 0 && (nums[marker] > 0) == direction) {
                int next = nextIndex(nums, marker);
                nums[marker] = 0;
                marker = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

if (nums[i] == 0) continue;Skip indices already processed or invalid.

bool direction = nums[i] > 0;Determine jump direction for cycle consistency.

int slowNext = nextIndex(nums, slow);Move slow pointer one step.

int fastNext = nextIndex(nums, fast);Move fast pointer one step first.

fastNext = nextIndex(nums, fastNext);Move fast pointer second step.

if (slow == fast) {Pointers meet, possible cycle detected.

if (slow == nextIndex(nums, slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

function circularArrayLoop(nums) {
    const n = nums.length;
    function nextIndex(i) {
        let next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        let slow = i, fast = i;
        const direction = nums[i] > 0;
        while (true) {
            let slowNext = nextIndex(slow);
            let fastNext = nextIndex(fast);
            if ((nums[slowNext] > 0) !== direction || (nums[fastNext] > 0) !== direction) break;
            fastNext = nextIndex(fastNext);
            if ((nums[fastNext] > 0) !== direction) break;
            slow = slowNext;
            fast = fastNext;
            if (slow === fast) {
                if (slow === nextIndex(slow)) break;
                return true;
            }
        }
        let marker = i;
        while (nums[marker] !== 0 && (nums[marker] > 0) === direction) {
            let next = nextIndex(marker);
            nums[marker] = 0;
            marker = next;
        }
    }
    return false;
}

// Example usage
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

if (nums[i] === 0) continue;Skip indices already processed or invalid.

const direction = nums[i] > 0;Determine jump direction for cycle consistency.

let slowNext = nextIndex(slow);Move slow pointer one step.

let fastNext = nextIndex(fast);Move fast pointer one step first.

fastNext = nextIndex(fastNext);Move fast pointer second step.

if (slow === fast) {Pointers meet, possible cycle detected.

if (slow === nextIndex(slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most once due to marking, so total time is linear. Space is constant as no extra data structures are used except pointers.

💡 For n=100000, this means about 100000 operations, efficient for large inputs.

Interview Verdict: Accepted

This is the optimal approach for cycle detection in this problem, balancing speed and space.

🧠

Optimized Fast-Slow with Early Exit and In-Place Marking

💡 This approach refines the fast-slow pointer method by adding early exits when direction changes and marking visited nodes in-place to avoid revisiting, improving runtime in practice.

Intuition

Stop traversing as soon as direction inconsistency or self-loop is detected, and mark visited nodes to skip them in future iterations.

Algorithm

1. Iterate over each index as a start point.
2. Skip if element is zero (already visited).
3. Use fast and slow pointers to detect cycle, stopping early if direction changes or self-loop.
4. If cycle detected, return true.
5. Mark all nodes in current traversal as zero to avoid reprocessing.
6. Return false if no cycle found.

💡 Early exits reduce unnecessary checks, and in-place marking saves space and time.

</>

Code

def circularArrayLoop(nums):
    n = len(nums)
    def next_index(i):
        return (i + nums[i]) % n

    for i in range(n):
        if nums[i] == 0:
            continue
        slow, fast = i, i
        direction = nums[i] > 0
        while True:
            slow_next = next_index(slow)
            fast_next = next_index(fast)
            if (nums[slow_next] > 0) != direction or (nums[fast_next] > 0) != direction:
                break
            fast_next = next_index(fast_next)
            if (nums[fast_next] > 0) != direction:
                break
            slow, fast = slow_next, fast_next
            if slow == fast:
                if slow == next_index(slow):
                    break
                return True
        marker = i
        while nums[marker] != 0 and (nums[marker] > 0) == direction:
            next_marker = next_index(marker)
            nums[marker] = 0
            marker = next_marker
    return False

# Example usage
if __name__ == '__main__':
    print(circularArrayLoop([2, -1, 1, 2, 2]))  # True
    print(circularArrayLoop([-1, 2]))  # False

Line Notes

def next_index(i):Helper to compute next index with wrap-around.

if nums[i] == 0:Skip indices already processed or invalid.

direction = nums[i] > 0Determine jump direction for cycle consistency.

slow_next = next_index(slow)Move slow pointer one step.

fast_next = next_index(fast)Move fast pointer one step first.

fast_next = next_index(fast_next)Move fast pointer second step.

if slow == fast:Pointers meet, possible cycle detected.

if slow == next_index(slow):Check for self-loop, invalid cycle.

nums[marker] = 0Mark visited indices to avoid reprocessing.

public class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            boolean direction = nums[i] > 0;
            while (true) {
                int slowNext = nextIndex(nums, slow);
                int fastNext = nextIndex(nums, fast);
                if ((nums[slowNext] > 0) != direction || (nums[fastNext] > 0) != direction) break;
                fastNext = nextIndex(nums, fastNext);
                if ((nums[fastNext] > 0) != direction) break;
                slow = slowNext;
                fast = fastNext;
                if (slow == fast) {
                    if (slow == nextIndex(nums, slow)) break;
                    return true;
                }
            }
            int marker = i;
            while (nums[marker] != 0 && (nums[marker] > 0) == direction) {
                int next = nextIndex(nums, marker);
                nums[marker] = 0;
                marker = next;
            }
        }
        return false;
    }

    private int nextIndex(int[] nums, int i) {
        int n = nums.length;
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.circularArrayLoop(new int[]{2, -1, 1, 2, 2})); // true
        System.out.println(sol.circularArrayLoop(new int[]{-1, 2})); // false
    }
}

Line Notes

if (nums[i] == 0) continue;Skip indices already processed or invalid.

boolean direction = nums[i] > 0;Determine jump direction for cycle consistency.

int slowNext = nextIndex(nums, slow);Move slow pointer one step.

int fastNext = nextIndex(nums, fast);Move fast pointer one step first.

fastNext = nextIndex(nums, fastNext);Move fast pointer second step.

if (slow == fast) {Pointers meet, possible cycle detected.

if (slow == nextIndex(nums, slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int nextIndex(const vector<int>& nums, int i) {
        int n = nums.size();
        int next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            bool direction = nums[i] > 0;
            while (true) {
                int slowNext = nextIndex(nums, slow);
                int fastNext = nextIndex(nums, fast);
                if ((nums[slowNext] > 0) != direction || (nums[fastNext] > 0) != direction) break;
                fastNext = nextIndex(nums, fastNext);
                if ((nums[fastNext] > 0) != direction) break;
                slow = slowNext;
                fast = fastNext;
                if (slow == fast) {
                    if (slow == nextIndex(nums, slow)) break;
                    return true;
                }
            }
            int marker = i;
            while (nums[marker] != 0 && (nums[marker] > 0) == direction) {
                int next = nextIndex(nums, marker);
                nums[marker] = 0;
                marker = next;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {2, -1, 1, 2, 2};
    vector<int> nums2 = {-1, 2};
    cout << boolalpha << sol.circularArrayLoop(nums1) << endl; // true
    cout << boolalpha << sol.circularArrayLoop(nums2) << endl; // false
    return 0;
}

Line Notes

if (nums[i] == 0) continue;Skip indices already processed or invalid.

bool direction = nums[i] > 0;Determine jump direction for cycle consistency.

int slowNext = nextIndex(nums, slow);Move slow pointer one step.

int fastNext = nextIndex(nums, fast);Move fast pointer one step first.

fastNext = nextIndex(nums, fastNext);Move fast pointer second step.

if (slow == fast) {Pointers meet, possible cycle detected.

if (slow == nextIndex(nums, slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

function circularArrayLoop(nums) {
    const n = nums.length;
    function nextIndex(i) {
        let next = (i + nums[i]) % n;
        if (next < 0) next += n;
        return next;
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        let slow = i, fast = i;
        const direction = nums[i] > 0;
        while (true) {
            let slowNext = nextIndex(slow);
            let fastNext = nextIndex(fast);
            if ((nums[slowNext] > 0) !== direction || (nums[fastNext] > 0) !== direction) break;
            fastNext = nextIndex(fastNext);
            if ((nums[fastNext] > 0) !== direction) break;
            slow = slowNext;
            fast = fastNext;
            if (slow === fast) {
                if (slow === nextIndex(slow)) break;
                return true;
            }
        }
        let marker = i;
        while (nums[marker] !== 0 && (nums[marker] > 0) === direction) {
            let next = nextIndex(marker);
            nums[marker] = 0;
            marker = next;
        }
    }
    return false;
}

// Example usage
console.log(circularArrayLoop([2, -1, 1, 2, 2])); // true
console.log(circularArrayLoop([-1, 2])); // false

Line Notes

if (nums[i] === 0) continue;Skip indices already processed or invalid.

const direction = nums[i] > 0;Determine jump direction for cycle consistency.

let slowNext = nextIndex(slow);Move slow pointer one step.

let fastNext = nextIndex(fast);Move fast pointer one step first.

fastNext = nextIndex(fastNext);Move fast pointer second step.

if (slow === fast) {Pointers meet, possible cycle detected.

if (slow === nextIndex(slow)) break;Check for self-loop, invalid cycle.

nums[marker] = 0;Mark visited indices to avoid reprocessing.

⏱

Complexity

TimeO(n)

SpaceO(1)

Early exits and marking reduce unnecessary checks, maintaining linear time and constant space.

💡 This approach is the most efficient and practical for large inputs.

Interview Verdict: Accepted

This is the best practical approach combining clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the fast-slow pointer approach with in-place marking (Approach 2 or 3) for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Fast and Slow Pointer	O(n)	O(1)	No	N/A	Code this for optimal cycle detection
3. Optimized Fast-Slow with Early Exit	O(n)	O(1)	No	N/A	Code this for best practical performance

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and definitions (cycle length, direction).Step 2: Present brute force simulation to show understanding.Step 3: Introduce fast and slow pointer technique for optimization.Step 4: Discuss in-place marking and early exits for further optimization.Step 5: Code the optimal approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests understanding of cycle detection, pointer manipulation, handling edge cases, and optimization skills.

Common Follow-ups

• What if the array is not circular? → Adjust next index calculation accordingly.
• Can you find the actual cycle start index? → Use cycle detection algorithms to find entry point.

💡 These follow-ups test deeper understanding of cycle detection and problem variations.

🔍

Pattern Recognition

When to Use

1) Problem involves cycles in sequences or arrays; 2) Next element is computed via index jumps; 3) Need to detect cycles efficiently; 4) Constraints require O(n) time and O(1) space.

Signature Phrases

'circular array''jump steps''cycle length > 1''same direction'

NOT This Pattern When

Problems involving simple array traversal or sorting without implicit next pointers

Similar Problems

Linked List Cycle - classic fast-slow pointer cycle detectionHappy Number - cycle detection in number sequences

Practice

1. You need to find the value of the node that is n positions from the end in a singly linked list. Which approach guarantees a single-pass solution with O(n) time complexity and O(1) extra space?

easy

A. Using a stack to store all nodes and then popping n times to get the target node.

B. Using two pointers where the fast pointer advances n steps ahead, then both move until fast reaches the end.

C. Calculating the length of the list first, then traversing again to the (length - n)th node.

D. Using a recursive function to traverse to the end and count back to the nth node.

Solution

1. Step 1: Understand the problem constraints

   The goal is to find the nth node from the end in a single pass with minimal extra space.

2. Step 2: Evaluate approaches

   Using two pointers with the fast pointer n steps ahead allows the slow pointer to land exactly on the target node when fast reaches the end, achieving O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer technique is classic for single-pass linked list problems [OK]

Hint: Two pointers with gap n solve in one pass [OK]

Common Mistakes:

• Confusing stack approach as single pass
• Using two passes instead of one
• Assuming recursion is O(1) space

2. Consider this buggy code snippet for finding the nth node from the end using two pointers. Which line contains the bug?

medium

A. Line 9: return statement returning slow pointer

B. Line 7: while loop condition

C. Line 3: for loop advancing fast pointer

D. Line 2: initializing slow pointer

Solution

1. Step 1: Analyze return statement

   The function returns the slow pointer node instead of its value, which is inconsistent with expected output.

2. Step 2: Confirm other lines are correct

   Fast pointer advances n-1 steps, loop condition is correct, and slow pointer initialization is standard.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Returning node instead of value causes confusion or errors [OK]

Hint: Return node.val, not node reference [OK]

Common Mistakes:

• Not checking if n > length
• Advancing fast pointer fewer steps
• Returning node instead of value

3. What is the space complexity of the recursive backtracking solution to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(log n) -- recursion divides the list in half each call

C. O(n) -- due to auxiliary arrays storing node references

D. O(n) -- due to recursion stack depth proportional to list length

Solution

1. Step 1: Identify recursion depth

   The recursion visits each node once, so the call stack depth is n.

2. Step 2: Understand space usage

   No extra arrays or data structures are used, but the recursion stack itself uses O(n) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Recursion stack proportional to list length n [OK]

Hint: Recursion stack uses O(n) space even if no extra arrays used [OK]

Common Mistakes:

• Assuming recursion uses constant space
• Confusing recursion with divide-and-conquer halving
• Thinking auxiliary arrays are used

4. Suppose the problem is modified so that the linked list is circular (the last node points back to the head), and you need to remove the nth node from the end. Which approach correctly adapts to this scenario?

hard

A. First detect the cycle length by traversing until you return to the start, then remove the (length - n)th node using two pointers.

B. Use the same recursive backtracking approach without changes; it works for circular lists.

C. Break the cycle by setting the last node's next to None, then apply the standard two-pointer method.

D. Use a hash set to track visited nodes and remove the nth node from the end by counting backwards.

Solution

1. Step 1: Detect cycle length

   In a circular list, length is unknown; traverse until returning to start to find length.

2. Step 2: Use two pointers with known length

   Once length is known, use two pointers with gap n+1 to remove the target node safely.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cycle length detection is necessary before removal [OK]

Hint: Must find cycle length before applying two-pointer removal [OK]

Common Mistakes:

• Applying recursion blindly on circular list causing infinite recursion
• Breaking cycle without restoring it, altering list structure
• Using hash sets unnecessarily increasing space

5. Suppose the problem is modified so that the linked list nodes can be reused multiple times in different parts (i.e., parts can share nodes). Which of the following changes to the original splitting algorithm correctly adapts to this new requirement?

hard

A. Split the list into k parts by creating new linked lists from scratch for each part, ignoring original links.

B. Keep the original algorithm but duplicate nodes when assigning to parts to avoid shared references.

C. Remove the step that breaks the link (current.next = null) after each part, allowing parts to share nodes.

D. Use a greedy approach assigning nodes to parts without precomputing sizes, since reuse allows overlap.

Solution

1. Step 1: Understand reuse requirement

   Nodes can appear in multiple parts, so links should not be broken to preserve shared nodes.

2. Step 2: Adapt algorithm

   Removing the link-breaking step allows parts to share nodes as required.

3. Step 3: Evaluate other options

   Duplicating nodes or creating new lists is unnecessary and inefficient; greedy without sizes breaks constraints.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Not breaking links enables node reuse [OK]

Hint: Remove link breaks to allow node reuse [OK]

Common Mistakes:

• Duplicating nodes unnecessarily
• Breaking links despite reuse
• Ignoring size constraints