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 are given a singly linked list that may contain a cycle. The task is to find the node where the cycle begins, if any. Which of the following approaches guarantees finding the cycle's start node in O(n) time and O(1) space?

easy

A. Use two pointers moving at different speeds to detect the cycle and then find the cycle start by resetting one pointer to head.

B. Use a depth-first search to detect back edges and identify the cycle start.

C. Use a hash set to store visited nodes and return the first repeated node.

D. Use a greedy approach to jump nodes and check for cycles by comparing node values.

Solution

1. Step 1: Understand cycle detection with two pointers

   The fast and slow pointer technique detects a cycle by moving fast pointer twice as fast as slow pointer. If they meet, a cycle exists.

2. Step 2: Find cycle start by resetting one pointer

   After detection, reset one pointer to head and move both one step at a time until they meet again; this meeting point is the cycle start node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach finds cycle start in O(n) time and O(1) space [OK]

Hint: Two pointers detect and locate cycle start efficiently [OK]

Common Mistakes:

• Believing hash set is O(1) space
• Using DFS which is not suitable for linked lists
• Greedy jumps fail to detect cycles

2. Consider the following Python code implementing Floyd's cycle detection and cycle start finding algorithm. Given the linked list: 1 -> 2 -> 3 -> 4 -> 2 (cycle starts at node with value 2), what value does the function return?

easy

A. 4

B. 3

C. 2

D. None

Solution

1. Step 1: Trace slow and fast pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet inside the cycle at node with value 3 or 4 after some iterations.

2. Step 2: Reset one pointer to head and move both one step at a time

   Both pointers meet at node with value 2, which is the cycle start.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle start node value is 2 as per algorithm [OK]

Hint: Cycle start found by meeting pointers after reset [OK]

Common Mistakes:

• Returning meeting point instead of cycle start
• Off-by-one error in pointer movement
• Returning None incorrectly

3. You are given a singly linked list and asked to reorder it so that the nodes are arranged in the order: first node, last node, second node, second last node, and so on. Which approach guarantees an optimal in-place solution with O(n) time and O(1) extra space?

easy

A. Use a brute force approach by storing all nodes in an array and then rearranging pointers.

B. Use dynamic programming to store intermediate reorder states and build the final list.

C. Recursively reorder the list by traversing to the end and merging nodes from both ends.

D. Find the middle of the list using fast and slow pointers, reverse the second half, then merge the two halves.

Solution

1. Step 1: Identify the problem constraints

   The problem requires reordering the list in-place with O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Brute force uses extra space, recursion uses O(n) stack space, and DP is not applicable here. The fast-slow pointer approach finds the middle, reverses the second half, and merges in-place efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Fast-slow pointer approach is classic for in-place reorder [OK]

Hint: Fast-slow pointer + reverse + merge is classic in-place reorder [OK]

Common Mistakes:

• Thinking recursion is O(1) space
• Using DP for linked list reorder
• Assuming array storage is in-place

4. What is the time complexity of the optimized iterative approach for deleting N nodes after skipping M nodes in a singly linked list of length n? Assume M and N are constants.

medium

A. O(n)

B. O(n * (M + N))

C. O(n^2)

D. O(n + M + N)

Solution

1. Step 1: Identify loop behavior

   The algorithm traverses the list once, moving forward by skipping M nodes and deleting N nodes repeatedly.

2. Step 2: Analyze complexity

   Since M and N are constants, each iteration moves forward by at least M+N nodes, so total steps proportional to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass traversal yields O(n) time complexity [OK]

Hint: Constant M, N means linear traversal dominates [OK]

Common Mistakes:

• Mistaking nested loops causing O(n*(M+N))
• Assuming quadratic due to inner loops
• Ignoring that M and N are constants

5. Suppose you want to find the middle node of a linked list, but the list is circular (the last node points back to the head). Which modification to the two-pointer approach correctly finds the middle node without infinite looping?

hard

A. Use the same two-pointer approach but add a visited set to detect cycles and stop when fast pointer revisits a node.

B. Use recursion to count nodes until the head is reached again, then find middle by index.

C. Convert the circular list to a linear list by breaking the cycle first, then apply the standard two-pointer approach.

D. Modify the loop to stop when fast or fast.next equals the head node, then return slow pointer.

Solution

1. Step 1: Understand circular list behavior

   In a circular list, fast pointer will loop infinitely unless we detect when it cycles back to head.

2. Step 2: Modify loop condition

   Stop when fast or fast.next equals head to avoid infinite loop; slow pointer will be at middle.

3. Step 3: Compare alternatives

   Visited set adds extra space; breaking cycle modifies input; recursion risks stack overflow.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stopping at head detects cycle end without extra space [OK]

Hint: Detect cycle by checking if fast pointer returns to head [OK]

Common Mistakes:

• Using visited set wastes space
• Breaking cycle modifies input
• Recursion risks stack overflow