Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

457. Circular Array Loop - Leetcode Solution

Problem Description

The Circular Array Loop problem asks you to determine whether a given circular array of integers contains a cycle that meets specific requirements.

  • You are given an array nums of length n, where each element is a nonzero integer. Positive numbers move you forward, negative numbers move you backward.
  • Array is circular: moving forward from the last element wraps to the first, and moving backward from the first wraps to the last.
  • A cycle must:
    • Be longer than one element (cannot be a single-element loop).
    • Consist only of moves in a single direction (all positive or all negative numbers).
    • Be reachable by starting from some index i and following the jumps indefinitely.
  • Return True if there is at least one such cycle; otherwise, return False.

Constraints:

  • 1 ≤ nums.length ≤ 5000
  • nums[i] ≠ 0 for all i

Thought Process

The problem at first seems like a classic cycle-detection problem, similar to those involving linked lists. However, the movement is dictated by the values in the array, and the array is circular. A brute-force approach would be to simulate the process from every index, but this would be inefficient.

The main challenges are:

  • Handling circular movement (wrapping indices).
  • Detecting cycles efficiently.
  • Ensuring cycles are longer than one element and in a single direction.
This suggests using a cycle detection algorithm, such as Floyd's Tortoise and Hare, but adapted to the constraints of the problem.

Solution Approach

Our goal is to efficiently detect a valid cycle as defined by the problem. Here is the step-by-step approach:

  1. Iterate through each index in the array as a potential starting point for a cycle.
  2. Use two pointers (slow and fast) for cycle detection, similar to Floyd's algorithm:
    • Both pointers start at the current index.
    • Move the slow pointer one step and the fast pointer two steps, wrapping around the array as needed.
  3. Direction Consistency: Before moving, check if the direction (sign) of the current and next value is the same. If not, break out, as the cycle must be in a single direction.
  4. Single-Element Cycle Check: If a pointer would move to itself (i.e., next == current), skip this path since cycles must be longer than one element.
  5. Mark Visited Elements: If no cycle is found from a starting index, mark all elements visited in this path as 0 to avoid redundant checks (since 0 is not allowed in the input).
  6. Return True if a valid cycle is found; otherwise, continue to the next index.
  7. Return False if no cycle is detected after checking all indices.

This approach ensures we only check each path once and avoid unnecessary repeated work, making the algorithm efficient.

Example Walkthrough

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

  1. Start at index 0: Value is 2 (move forward).
    • Next index: (0 + 2) % 5 = 2
    • Next value: 1 (still forward)
    • Next index: (2 + 1) % 5 = 3
    • Next value: 2 (still forward)
    • Next index: (3 + 2) % 5 = 0
    • We are back to index 0, and the cycle length is > 1, all moves are forward.
    Valid cycle found! Return True.
  2. If no valid cycle is found, we would mark visited elements and try the next starting index. But in this example, we have already found a solution.

Time and Space Complexity

Brute-force approach: For each starting index, simulate the process, which could take up to O(n) time per index, for a total of O(n^2).

Optimized approach (with marking):

  • Each element is visited at most twice: once in cycle detection, once when marked as visited.
  • Total time complexity: O(n).
  • Space complexity: O(1) extra space, as we only use pointers and modify the input array in-place (except for recursion stack or explicit visited arrays in some languages).

Summary

The Circular Array Loop problem is a specialized cycle-detection challenge with constraints on direction and length. By adapting Floyd's cycle detection algorithm and marking visited elements, we can efficiently check for valid cycles in O(n) time and O(1) space. The key insights are handling circular indexing, ensuring direction consistency, and avoiding repeated work by marking visited paths.

Code Implementation

class Solution:
    def circularArrayLoop(self, 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:
                # Move slow pointer one step
                next_slow = next_index(slow)
                # Move fast pointer two steps
                next_fast = next_index(fast)
                if nums[next_fast] * nums[fast] <= 0 or nums[next_fast] == 0:
                    break
                next_fast = next_index(next_fast)
                if nums[next_fast] * nums[fast] <= 0 or nums[next_fast] == 0:
                    break

                # Check direction
                if nums[next_slow] * nums[i] <= 0 or nums[next_fast] * nums[i] <= 0:
                    break

                slow = next_slow
                fast = next_fast

                if slow == fast:
                    if slow == next_index(slow):
                        break  # one-element loop
                    return True

            # Mark all nodes in the current path as 0
            j = i
            while nums[j] * nums[i] > 0:
                next_j = next_index(j)
                nums[j] = 0
                j = next_j

        return False
      
class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        auto next = [&](int i) {
            return (i + nums[i] % n + n) % n;
        };

        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) continue;
            int slow = i, fast = i;
            bool dir = nums[i] > 0;

            while (true) {
                int next_slow = next(slow);
                int next_fast = next(fast);
                if (nums[next_fast] * nums[fast] <= 0 || nums[next_fast] == 0) break;
                next_fast = next(next_fast);
                if (nums[next_fast] * nums[fast] <= 0 || nums[next_fast] == 0) break;

                if (nums[next_slow] * nums[i] <= 0 || nums[next_fast] * nums[i] <= 0) break;

                slow = next_slow;
                fast = next_fast;

                if (slow == fast) {
                    if (slow == next(slow)) break;
                    return true;
                }
            }
            // Mark visited
            int j = i;
            while (nums[j] * nums[i] > 0) {
                int next_j = next(j);
                nums[j] = 0;
                j = next_j;
            }
        }
        return false;
    }
};
      
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 dir = nums[i] > 0;
            while (true) {
                int nextSlow = ((slow + nums[slow]) % n + n) % n;
                int nextFast = ((fast + nums[fast]) % n + n) % n;
                if (nums[nextFast] * nums[fast] <= 0 || nums[nextFast] == 0) break;
                nextFast = ((nextFast + nums[nextFast]) % n + n) % n;
                if (nums[nextFast] * nums[fast] <= 0 || nums[nextFast] == 0) break;

                if (nums[nextSlow] * nums[i] <= 0 || nums[nextFast] * nums[i] <= 0) break;

                slow = nextSlow;
                fast = nextFast;

                if (slow == fast) {
                    if (slow == ((slow + nums[slow]) % n + n) % n) break;
                    return true;
                }
            }
            // Mark visited
            int j = i;
            while (nums[j] * nums[i] > 0) {
                int nextJ = ((j + nums[j]) % n + n) % n;
                nums[j] = 0;
                j = nextJ;
            }
        }
        return false;
    }
}
      
var circularArrayLoop = function(nums) {
    const n = nums.length;
    const nextIndex = (i) => ((i + nums[i]) % n + n) % n;

    for (let i = 0; i < n; i++) {
        if (nums[i] === 0) continue;
        let slow = i, fast = i;
        const dir = nums[i] > 0;

        while (true) {
            let nextSlow = nextIndex(slow);
            let nextFast = nextIndex(fast);
            if (nums[nextFast] * nums[fast] <= 0 || nums[nextFast] === 0) break;
            nextFast = nextIndex(nextFast);
            if (nums[nextFast] * nums[fast] <= 0 || nums[nextFast] === 0) break;

            if (nums[nextSlow] * nums[i] <= 0 || nums[nextFast] * nums[i] <= 0) break;

            slow = nextSlow;
            fast = nextFast;

            if (slow === fast) {
                if (slow === nextIndex(slow)) break;
                return true;
            }
        }
        // Mark visited
        let j = i;
        while (nums[j] * nums[i] > 0) {
            let nextJ = nextIndex(j);
            nums[j] = 0;
            j = nextJ;
        }
    }
    return false;
};