Problem Statement

• LeetCode 457 Circular Array Loop: Cycle Detection with Direction Consistency

Given an array where each element represents a step size, you start at any index and follow the steps. The goal is to find if there's a cycle that:

• Contains more than one element
• Maintains consistent direction (all positive or all negative steps)

Algorithm Walkthrough

Core Strategy: Uses Floyd's cycle detection algorithm (slow/fast pointers) with additional optimizations.

public boolean circularArrayLoop(int[] nums) {
        int n = nums.length;
        if (n == 1)
            return false;

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                continue;
            }

            // slow/fast pointer approach for cycle detection
            int j = i, k = getIndex(i, nums);

            // Continue while direction is consistent
            while (nums[k] * nums[i] > 0 && nums[getIndex(k, nums)] * nums[i] > 0) {
                if (j == k) {
                    // Check for loop with only one element (invalid)
                    if (j == getIndex(j, nums)) {
                        break;
                    }
                    return true;
                }
                j = getIndex(j, nums);
                k = getIndex(getIndex(k, nums), nums);
            }

            // Loop not found, set all elements along the way to 0
            // This optimization prevents checking the same path again
            j = i;
            int val = nums[i];
            while (nums[j] * val > 0) {
                int next = getIndex(j, nums);
                nums[j] = 0;
                j = next;
            }
        }
        return false;
    }

    /**
     * Helper method to get the next index in circular array
     * Handles both positive and negative movements
     */
    public int getIndex(int i, int[] nums) {
        int n = nums.length;
        return i + nums[i] >= 0 ? (i + nums[i]) % n : n + ((i + nums[i]) % n);
    }

Main Logic Flow

1. Initial Setup: For each starting position i, check if it can lead to a valid cycle
2. Direction Consistency Check: nums[k] * nums[i] > 0 ensures all steps in the potential cycle have the same sign (same direction)
3. Cycle Detection:
   • j (slow pointer) moves one step at a time
   • k (fast pointer) moves two steps at a time
   • If they meet (j == k), a cycle is detected

Key Functions

getIndex(i, nums): Handles circular array navigation

• For positive steps: (i + nums[i]) % n
• For negative steps: n + ((i + nums[i]) % n) ensures positive result

Important Edge Cases

1. Single Element Loop: if (j == getIndex(j, nums)) prevents counting a self-loop as valid
2. Direction Changes: The while condition breaks if direction changes mid-path
3. Optimization: After checking a path, it marks all visited elements as 0 to avoid redundant checks

Example Walkthrough

For array [2, -1, 1, 2, 2]:

• Starting at index 0: 0 → 2 → 3 → 0 (valid cycle of length 3)
• All steps are positive, so direction is consistent
• Returns true

Time Complexity: O(n)

Why O(n) and not O(n²)?

Although there's a nested structure (outer loop × inner while loop), the key insight is that each element is visited at most a constant number of times due to the optimization:

1. First Visit: During cycle detection with Floyd's algorithm
2. Second Visit: When marking elements as 0 in the cleanup phase
3. Future Visits: Skipped because nums[i] == 0 check continues immediately

Detailed Analysis:

• Outer loop: O(n) iterations
• Inner while loop: Appears to be O(n) per iteration, but...
• Optimization: After checking a path from index i, all elements along that path are set to 0
• This means each element participates in cycle detection at most once
• Total work across all iterations: O(n)

Space Complexity: O(1)

Constant Space Usage:

• Only uses a few integer variables: i, j, k, n, val, next
• No additional data structures (arrays, lists, etc.)
• The algorithm modifies the input array in-place by setting visited elements to 0

Trade-off:

• Destructive: Modifies the original array
• Non-destructive alternative: Would require O(n) space for a visited array, making space complexity O(n)

Summary

• Time: O(n) - each element processed at most twice
• Space: O(1) - only uses constant extra variables

This makes it an optimal solution for the problem constraints, achieving linear time with constant space through clever in-place marking of visited elements.