Cycle in a Circular Array (Directional Fast-Slow Pointers)

• Circular array loop – detecting a cycle in an array where each index jumps to another index via its value, wrapping around with modular arithmetic.
• Floyd's fast-slow pointers – slow takes one jump, fast takes two; if they meet, a cycle exists.
• Direction guard – all elements in a valid cycle must share the same sign (all forward or all backward).
• Length guard – a cycle of length one (a slot pointing to itself) is invalid and must be rejected.
• Modular wrap – next index = ((current + nums[current]) % n + n) % n to handle both positive and negative jumps.

What is the Circular Array Loop problem?

Given a circular array of non-zero integers, each value represents a jump distance. Positive values jump forward, negative values jump backward, and jumps wrap around the array. Determine whether there is a cycle where all movements go in the same direction and the cycle length exceeds one.

At the National Bank of India, Pankaj's settlement routing system has a ring of processing slots. Each slot forwards a message a certain number of slots ahead or behind. A misconfiguration could create a loop where messages circulate forever.

How does the jump computation work?

Each index i jumps to the next index computed with modular arithmetic:

private static int nextIndex(int[] nums, int current) {
    int n = nums.length;
    int next = ((current + nums[current]) % n + n) % n;
    return next;
}

The double-modulo pattern ((value % n) + n) % n ensures the result is always non-negative, handling both forward and backward jumps correctly.

How does Floyd's fast-slow detection apply here?

For each starting index, run a slow pointer (one jump) and a fast pointer (two jumps). If they meet, a cycle exists. Two extra guards apply at every move.

package com.bank.service;

public class CircularArrayLoop {
    public static boolean hasCircularLoop(int[] nums) {
        int n = nums.length;

        for (int i = 0; i < n; i++) {
            boolean isForward = nums[i] > 0;
            int slow = i, fast = i;

            do {
                slow = getNext(nums, slow, isForward);
                if (slow == -1) break;
                fast = getNext(nums, fast, isForward);
                if (fast == -1) break;
                fast = getNext(nums, fast, isForward);
                if (fast == -1) break;
            } while (slow != fast);

            if (slow != -1 && slow == fast) {
                return true;
            }
        }
        return false;
    }

    private static int getNext(int[] nums, int current, boolean isForward) {
        boolean direction = nums[current] > 0;
        if (direction != isForward) return -1; // direction changed

        int n = nums.length;
        int next = ((current + nums[current]) % n + n) % n;
        if (next == current) return -1; // single-element self-loop

        return next;
    }

    public static void main(String[] args) {
        int[] slots = {2, -1, 1, 2, 2};
        System.out.println("Has cycle: " + hasCircularLoop(slots));

        int[] noLoop = {-1, 2};
        System.out.println("Has cycle: " + hasCircularLoop(noLoop));
    }
}

Has cycle: true
Has cycle: false

What are the two guard rules?

Guard 1 : Direction consistency. Fix the sign of the starting value. If any jump lands on a value with a different sign, abandon the path. A valid cycle must travel in a single direction.

Guard 2 : No single-element loop. If a jump returns to the same index in one step, the cycle length is one, which is invalid. Abandon the path.

// Guard 1: direction check
if ((nums[current] > 0) != isForward) return -1;

// Guard 2: self-loop check
if (next == current) return -1;

Why mark visited indices for optimization?

When a starting index leads to a failed path (no valid cycle), every index visited on that path also cannot start a valid cycle. Marking them avoids re-exploration.

// After a failed path starting at index i:
// Walk the path again and mark each index as visited
int j = i;
while (true) {
    int next = ((j + nums[j]) % n + n) % n;
    nums[j] = 0; // mark as visited (zero means skip)
    j = next;
    if (j == i) break;
}

This optimization improves the amortized time because each index is explored at most once across all starting points.

What is the time and space complexity?

| Approach | Time | Space |
|---|---|---|
| With visited marking | O(n) amortized | O(1) |
| Without marking | O(n^2) worst case | O(1) |

What are common mistakes?

The most common mistake is forgetting the direction guard, which makes the algorithm report cycles that mix forward and backward jumps.

// Wrong: no direction check
private static int getNext(int[] nums, int current) {
    int n = nums.length;
    return ((current + nums[current]) % n + n) % n;
}

// Correct: direction check included
private static int getNext(int[] nums, int current, boolean isForward) {
    if ((nums[current] > 0) != isForward) return -1;
    int n = nums.length;
    int next = ((current + nums[current]) % n + n) % n;
    if (next == current) return -1;
    return next;
}

What are the edge cases?

• Array of length 1: a single element cannot form a valid cycle (length must exceed one), so return false.
• All same direction, all pointing one step ahead: every starting point leads to a full-circle loop.
• Alternating signs: no valid cycle exists because the direction guard will fail.

What should a senior engineer know?

The two guard rules are what make this harder than plain linked-list cycle detection. Interviewers specifically check that you enforce both the same-direction requirement and the length-greater-than-one requirement rather than just reusing the vanilla fast-slow template.

The modular arithmetic must be written carefully for negative jumps. The standard idiom is ((current + nums[current]) % n + n) % n, which always produces a non-negative index.

What are common interview follow-up questions?

• Can you do it in O(1) space? (Yes, by mutating the array to mark visited indices.)
• What if zeros are allowed? (Zeros would create instant self-loops, so they are excluded by the problem statement.)
• How would you adapt this for a doubly-linked circular structure? (Floyd's algorithm works directly without direction guards.)