Fast & Slow PointersHardO(n²) time · O(1) space

Cycle in a Circular Array

Mahabharata — The Disc of Sudarshana — Detecting Infinite Loops in the Battlefield Orders

एकदिशि प्रवर्तेत एकमेव वर्तुलम्। दीर्घं चेत् चक्रमस्त्येव — लघु व्यर्थं न गणयेत्॥

*The true cycle moves in one direction and has length greater than one. Long it must be — a trivial self-loop counts for naught.*

The Story

In the divine armory of Vaikuntha, Lord Vishnu's Sudarshana Chakra was the ultimate weapon — a spinning disc that returned to its master after fulfilling its mission. But before it could be deployed, Krishna's charioteer Daruka had to verify that the weapon's deployment path formed a valid cycle: it must travel in a consistent direction (all forward or all backward), and the cycle must be longer than a single node (a weapon that immediately turns back on itself is useless).

The battlefield orders were encoded as a circular array `nums` of length n. Each position `i` held a value telling the warrior at that position how many steps to advance (positive = forward, negative = backward). The array was circular — stepping past index n-1 wraps to index 0, stepping before 0 wraps to index n-1.

For each starting position, Daruka needed to determine: does following these orders create a valid cycle?

"The conditions for a valid cycle," Daruka announced, reading from the divine scroll: 1. All elements in the cycle must have the same sign (all positive or all negative — consistent direction) 2. The cycle length must be greater than 1 (a single element pointing to itself is not a valid cycle)

"How do we check this efficiently?" his aide asked.

"For each starting position i, run fast and slow pointers as if it's a linked list," Daruka explained. "The 'next' of position i is `(i + nums[i]) % n`, with proper handling of negative modulo."

"If slow and fast meet and the cycle is valid (same direction, length > 1), return true. If during traversal we detect a direction change, abort — this start position cannot produce a valid cycle."

"But what about revisiting positions we've already determined are dead ends?" the aide asked.

"Mark them as 0 — a position that leads to no valid cycle. When a pointer lands on 0, we know to abort. This is our visited-marking optimization."

Daruka demonstrated with `nums = [2, -1, 1, 2, 2]`:

**Start at i=0 (nums[0]=2, forward direction):** - next(0) = (0+2)%5 = 2. nums[2]=1 (positive, same direction ✓) - slow=next(0)=2, fast=next(next(0))=next(2)=3 - slow=next(2)=3, fast=next(next(3))=next(0)=2 - slow=next(3)=0, fast=next(next(2))=next(3)=0 - slow==fast==0! Cycle found. But check: is the cycle valid? - Direction: nums[0]=2>0, nums[2]=1>0, nums[3]=2>0 ✓ (all positive) - Length > 1: slow took 3 steps to meet fast, so cycle length > 1 ✓ - **Return true!**

**Start at i=1 (nums[1]=-1, backward direction):** - next(1) = (1-1+5)%5 = 0. But nums[0]=2 (positive!) — direction changed! - Abort this start, mark i=1 as 0.

The key additional validity check for cycle length = 1: when slow == fast, verify that `next(slow) != slow`. If next(slow) == slow, it means nums[slow] is a multiple of n (the element points back to itself modulo n) — a cycle of length 1, which is invalid.

"The Sudarshana Chakra spins," Daruka said, watching the glowing disc. "Its path must be consistent — always forward or always backward — and must cover more than a single position. Otherwise, it is not a true cycle. It is merely a soldier standing in place."

The detection algorithm was deployed across all n starting positions. For the array [2,-1,1,2,2], starting at position 0 yielded a valid forward cycle through positions [0,2,3,0]. The weapon was cleared for deployment.

This is the Fast & Slow Pointer technique for detecting cycles in a circular array.

Daruka's First Instinct

For each starting position, follow the path using a HashSet to detect if we revisit a node. Check direction consistency and cycle length. O(n) per start × O(n) starts = O(n²) time, O(n) space.

java

public boolean circularArrayLoopBruteForce(int[] nums) {
    int n = nums.length;
    
    for (int start = 0; start < n; start++) {
        Set<Integer> visited = new HashSet<>();
        int cur = start;
        boolean forward = nums[start] > 0;  // Expected direction
        
        while (true) {
            // Check direction consistency
            if ((nums[cur] > 0) != forward) break;
            // Check self-loop (cycle length 1)
            int next = ((cur + nums[cur]) % n + n) % n;
            if (next == cur) break;
            // Check if we've seen this node (cycle)
            if (visited.contains(next)) return true;
            visited.add(cur);
            cur = next;
        }
    }
    return false;
}

Daruka's Wisdom

Daruka's optimization: use fast & slow pointers for cycle detection. For each start, advance slow by 1 step and fast by 2 steps in the circular array. Apply validity checks (same direction, no self-loop) at each step. Mark dead-end positions as `nums[i] = 0` to avoid re-processing them. This turns O(n) per start into an amortized improvement, though worst case remains O(n²).

java

public boolean circularArrayLoop(int[] nums) {
    int n = nums.length;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] == 0) continue;  // Already marked as dead end
        
        int slow = i, fast = i;
        boolean forward = nums[i] > 0;  // Direction for this starting position
        
        do {
            // Advance slow one step
            slow = nextIndex(nums, slow, forward, n);
            // Advance fast two steps
            fast = nextIndex(nums, fast, forward, n);
            if (fast != -1) fast = nextIndex(nums, fast, forward, n);
        } while (slow != -1 && fast != -1 && slow != fast);
        
        if (slow != -1 && slow == fast) {
            return true;  // Valid cycle found
        }
        
        // Mark all positions in this path as dead ends
        int j = i;
        while (nums[j] != 0 && (nums[j] > 0) == forward) {
            int next = nextIndex(nums, j, forward, n);
            nums[j] = 0;
            j = (next == -1) ? i : next;  // Don't go past dead ends
            if (j == i) break;
        }
    }
    return false;
}

private int nextIndex(int[] nums, int cur, boolean forward, int n) {
    boolean curForward = nums[cur] > 0;
    // Direction change? Invalid path
    if (curForward != forward) return -1;
    
    int next = ((cur + nums[cur]) % n + n) % n;  // Handle negative mod
    // Cycle length 1? Invalid
    if (next == cur) return -1;
    
    return next;
}

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

Step-by-Step Walkthrough

nums = [2, -1, 1, 2, 2]

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
START i=0, direction=forward (nums[0]=2>0)

next(0): (0+2)%5=2, nums[2]=1>0 same dir ✓, 2≠0 ✓ → 2
next(2): (2+1)%5=3, nums[3]=2>0 same dir ✓, 3≠2 ✓ → 3
next(3): (3+2)%5=0, nums[0]=2>0 same dir ✓, 0≠3 ✓ → 0

Do-while iteration:
  slow=next(0)=2, fast=next(next(0))=next(2)=3
  slow≠fast, continue
  slow=next(2)=3, fast=next(next(3))=next(0)=2
  slow≠fast, continue  
  slow=next(3)=0, fast=next(next(2))=next(3)=0
  slow==fast==0 → cycle!

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Valid cycle check:
  Cycle contains: 0→2→3→0 (all positive/forward) ✓
  Cycle length = 3 > 1 ✓

✅ Return true

Deep Insight

**Why is cycle length 1 invalid?** If `next(i) == i`, the element `nums[i]` is a nonzero multiple of n. The warrior would spin on the spot — this is a self-loop, not a cycle worth counting. The problem specifically says a cycle must have length > 1.

**Why must all elements be the same direction?** A cycle where some steps go forward and some go backward would mean the 'wheel' oscillates — not a true unidirectional cycle. The Sudarshana Chakra spins in one direction.

**The negative modulo issue:** `(i + nums[i]) % n` can be negative in Java when `nums[i]` is negative. The fix: `((i + nums[i]) % n + n) % n`

**Why mark dead ends as 0?** Any position that leads to an invalid path (direction change or self-loop) can never be part of a valid cycle for any starting point. Setting `nums[i]=0` prevents redundant traversals.

**Complexity note:** Although we try O(n) starts, the marking of dead ends means each position is visited at most twice, giving an amortized O(n) total — though worst case remains O(n²) without the marking optimization.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(n)	n starts × n path length, HashSet per start
Optimal	O(n²)	O(1)	n starts, but dead-end marking avoids many re-traversals; in-place modification

Pattern Recognition

✅ Circular array where each element points to next position
✅ Need to detect a cycle with validity constraints
✅ O(1) space required
✅ Validity: same-direction cycle of length > 1

**LeetCode Trigger Phrases:**
→ "circular array" + "detect cycle"
→ "all elements... same direction" + "length greater than 1"
→ "nums[i] moves forward/backward i+nums[i] steps"

Bhagavad Gita 16.7

प्रवृत्तिं च निवृत्तिं च जना न विदुरासुराः। न शौचं नापि चाचारो न सत्यं तेषु विद्यते॥

The demonic do not know what to do and what to refrain from. Neither purity nor right conduct nor truth is found in them.

Connection: The invalid cycles in this problem — those that change direction or form self-loops — mirror the description of demonic behavior in the Gita: inconsistency in direction (going forward then backward with no purpose), self-referential loops with no progress. The valid cycle, like dharmic action, moves consistently in one direction with substance and length. The algorithm's validity checks distinguish the purposeful cycles (dharmic) from the false ones (adharmic).