Circular Array Loop

• Iterate through each index i from 0 to n-1, treating it as a potential starting point of a cycle.
• For each starting index i, initialize a new HashSet called path_visited to track the indices in the current traversal path.
• Determine the direction of movement (forward for positive nums[i], backward for negative) and store it.
• Start a traversal from curr = i.
• In a loop, calculate the next index using the formula (curr + nums[curr] % n + n) % n.
• Check for invalid cycle conditions:
  • Self-loop: If next == curr, the cycle has a length of 1, which is invalid. Break the inner loop.
  • Mixed directions: If the sign of nums[next] does not match the initial direction, the cycle is invalid. Break the inner loop.
• Check if next is already in path_visited. If it is, a cycle has been found. Since self-loops are already handled, this cycle's length is greater than 1. Return true.
• If no cycle is found yet, add curr to path_visited and update curr = next to continue the traversal.
• If the outer loop completes without finding any valid cycles, return false.

The brute-force method systematically checks every possible starting point for a cycle. For each index i in the nums array, we begin a new path traversal.

We use a HashSet to keep track of the nodes visited within the current traversal. This is crucial for detecting when a path loops back on itself. We also establish the required direction of movement (forward or backward) based on the value of nums[i].

We then follow the jumps from index to index. At each step, we perform three checks:

1. Direction Consistency: The value at the next index must have the same sign as the starting value. If not, this path cannot form a valid cycle, and we abandon it.
2. Self-Loop: The next index cannot be the same as the current index. This would be a cycle of length 1, which is not allowed.
3. Cycle Detection: If the next index is already in our HashSet, it means we have re-visited a node in the current path, forming a cycle of length greater than 1. We can immediately return true.

If a path terminates due to a direction change or a self-loop, we move on to the next starting index i+1. If we check all possible starting points without finding a valid cycle, we return false.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean circularArrayLoop(int[] nums) {6        int n = nums.length;7        for (int i = 0; i < n; i++) {8            Set<Integer> path = new HashSet<>();9            int curr = i;10            boolean isForward = nums[i] > 0;11 12            while (true) {13                // Check for direction change14                if ((nums[curr] > 0) != isForward) {15                    break;16                }17 18                // Add current node to path and calculate next19                path.add(curr);20                int next = (curr + nums[curr] % n + n) % n;21 22                // Check for self-loop23                if (next == curr) {24                    break;25                }26 27                // Check if we've completed a cycle28                if (path.contains(next)) {29                    return true;30                }31                32                curr = next;33            }34        }35        return false;36    }37}

• Initialize a global boolean array visited of size n to all false.
• Iterate through each index i from 0 to n-1.
• If visited[i] is true, it means this index was part of a previously checked path, so we can skip it.
• If visited[i] is false, start a new traversal from i.
• For this new traversal, use a temporary path_visited HashSet to detect cycles within the current path only.
• As you traverse from a node curr, first check if it's in path_visited. If so, you've found a valid cycle, return true.
• Then check if it's in the global visited array. If so, this path merges into an old, invalid path. Stop this traversal.
• Mark visited[curr] = true and add curr to path_visited.
• Calculate the next index and check for validity (no self-loops, consistent direction).
• If the path is invalid, break the inner loop. The nodes visited so far are now marked in the global visited array, preventing them from being used as starting points again.
• If the outer loop finishes, return false.

The core idea is to remember which nodes we've already analyzed. We introduce a boolean array, visited, of the same size as nums.

We loop through each index i from 0 to n-1. Before starting a traversal from i, we check visited[i]. If it's true, we immediately continue to i+1, because i has already been part of a path that we've fully explored.

If visited[i] is false, we proceed with a traversal. We still use a temporary HashSet, pathVisited, to detect cycles specific to the current path. As we visit each node curr in this new path, we mark it in both visited[curr] and pathVisited.

If our current path intersects with a previously visited node (i.e., visited[curr] is true but curr is not in pathVisited), it means our current path merges into a path that was already confirmed to not contain a valid cycle. We can therefore terminate the current traversal.

This optimization ensures that every node in the array is visited and processed only once across all traversals, bringing the time complexity down from O(n^2) to O(n).

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public boolean circularArrayLoop(int[] nums) {6        int n = nums.length;7        boolean[] visited = new boolean[n];8 9        for (int i = 0; i < n; i++) {10            if (visited[i]) {11                continue;12            }13            14            Set<Integer> pathVisited = new HashSet<>();15            int curr = i;16            boolean isForward = nums[i] > 0;17 18            while (true) {19                if (pathVisited.contains(curr)) {20                    // Cycle found in the current path21                    return true;22                }23                if (visited[curr]) {24                    // Merged into a path that was already checked and found no valid cycle25                    break;26                }27 28                visited[curr] = true;29                pathVisited.add(curr);30 31                int next = (curr + nums[curr] % n + n) % n;32 33                if (next == curr || (nums[next] > 0) != isForward) {34                    break;35                }36                37                curr = next;38            }39        }40        return false;41    }42}

• Iterate through each index i from 0 to n-1.
• If nums[i] is 0, this index belongs to a path that has already been processed and found to be invalid. Skip it.
• Initialize two pointers, slow and fast, both to i. Also, determine the required direction is_forward from nums[i].
• Enter a loop to move the pointers:
  • Advance slow by one step using a helper function getNext.
  • Advance fast by two steps, calling getNext twice.
  • The getNext helper function should check for path validity. It takes the current index, the array, and the required direction. It returns the next index if the move is valid (same direction, not a self-loop), and a special value (e.g., -1) if it's invalid.
  • If at any point slow or fast becomes -1, the path is invalid. Break the pointer-moving loop.
  • If slow and fast become equal (and are not -1), a valid cycle has been found. Return true.
• If the pointer-moving loop terminates without returning true, it means the path starting from i is invalid. Mark this entire path by traversing it again from i and setting the values nums[j] to 0.
• If the main loop finishes, no valid cycles were found. Return false.

This approach treats the array as a functional graph where each index is a node with exactly one outgoing edge. We are looking for a cycle in this graph that meets the problem's criteria.

We iterate through each index i. If nums[i] is not 0 (our mark for a visited/invalid path), we start a cycle detection process from i.

Two pointers, slow and fast, are initialized at i. In each iteration, slow advances one step and fast advances two steps. A helper function, getNext, calculates the next index while also enforcing the problem's rules:

1. Consistent Direction: The move is only valid if nums[next_index] has the same sign as nums[i].
2. No Self-Loops: The move is invalid if next_index is the same as current_index. If a move is invalid, getNext returns a sentinel value like -1, causing the search along that path to terminate.

If slow and fast pointers meet at a valid index, we have found a cycle that adheres to all conditions, and we can return true.

If the search from i terminates without finding a cycle (because a pointer hit an invalid move), we must prevent this path from being re-analyzed. We do this by traversing the path again from i and setting each nums value to 0. This ensures that each node in the graph is part of a fast/slow pointer search at most once, guaranteeing an overall O(n) time complexity with O(1) extra space.

1class Solution {2    public boolean circularArrayLoop(int[] nums) {3        int n = nums.length;4        if (n <= 1) {5            return false;6        }7 8        for (int i = 0; i < n; i++) {9            // Skip if element is 0, as it indicates a processed path10            if (nums[i] == 0) {11                continue;12            }13 14            int slow = i, fast = i;15            boolean isForward = nums[i] > 0;16 17            do {18                slow = getNext(slow, nums, n, isForward);19                fast = getNext(fast, nums, n, isForward);20                if (fast != -1) {21                    fast = getNext(fast, nums, n, isForward);22                }23            } while (slow != -1 && fast != -1 && slow != fast);24 25            if (slow != -1 && slow == fast) {26                return true;27            }28 29            // Mark the path as visited (invalid) by setting elements to 030            int curr = i;31            boolean currentDirection = nums[curr] > 0;32            while (currentDirection == isForward && nums[curr] != 0) {33                int next = (curr + nums[curr] % n + n) % n;34                nums[curr] = 0;35                curr = next;36            }37        }38 39        return false;40    }41 42    private int getNext(int curr, int[] nums, int n, boolean isForward) {43        // A 0 indicates a previously visited invalid path44        if (nums[curr] == 0) {45            return -1;46        }47        // Check for direction consistency48        if ((nums[curr] > 0) != isForward) {49            return -1;50        }51        52        int next = (curr + nums[curr] % n + n) % n;53        54        // Check for self-loop55        if (next == curr) {56            return -1;57        }58        59        return next;60    }61}