LeetCode Solutions Blog

Circular Array Loop

Number: 457

Difficulty: Medium

Paid? No

Problem Description

Given a circular array of non-zero integers where each element indicates how many steps to move (forward if positive, backward if negative), determine if there exists a cycle in the array. A cycle is defined as a sequence of indices where each move follows the same direction (all positive or all negative) and the cycle length is greater than 1.

Key Insights

The array is circular; use modulo arithmetic to compute the next index.
A valid cycle must contain moves in a consistent direction (either all positive or all negative).
Cycles of length 1 (self-loops) are not allowed.
The fast and slow pointers (Floyd’s Cycle Detection) can be used to efficiently check for cycles.
Marking visited elements (by setting them to 0) prevents reprocessing and ensures O(1) extra space.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution iterates over each index and, for each unvisited index, employs the fast and slow pointers to detect a cycle. The pointers move in the array using the next index computed by taking the modulo of the current index plus the step value. If the fast and slow pointers meet, then a cycle exists provided it is not a self-loop and the movement direction remains consistent. Finally, all elements along the current exploration path are marked as visited to avoid redundant work.

Code Solutions

def circularArrayLoop(nums):
    n = len(nums)

    def next_index(i):
        # Calculate the next index; ensure cyclic wrapping using modulo arithmetic.
        return (i + nums[i]) % n

    for i in range(n):
        if nums[i] == 0:
            continue  # Skip visited elements.

        # Determine the movement direction for the current cycle.
        direction = nums[i] > 0

        slow, fast = i, i
        while True:
            # Move slow pointer one step.
            next_slow = next_index(slow)
            # Check direction consistency and make sure it's not a one-element loop.
            if (nums[next_slow] > 0) != direction or next_slow == slow:
                break

            # Move fast pointer one step.
            next_fast = next_index(fast)
            if (nums[next_fast] > 0) != direction or next_fast == fast:
                break
            # Move fast pointer a second step.
            next_fast = next_index(next_fast)
            if (nums[next_fast] > 0) != direction or next_fast == fast:
                break

            slow, fast = next_slow, next_fast
            if slow == fast:
                # Check cycle length > 1.
                if slow == next_index(slow):
                    break
                return True

        # Mark the elements visited during this exploration.
        marker = i
        while nums[marker] != 0 and (nums[marker] > 0) == direction:
            next_marker = next_index(marker)
            nums[marker] = 0  # Mark as visited.
            marker = next_marker

    return False

# Example usage:
# print(circularArrayLoop([2, -1, 1, 2, 2]))  # Output: True
# print(circularArrayLoop([-1, -2, -3, -4, -5, 6]))  # Output: False