#457

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Circular Array Loop

Detect whether a circular array contains a loop of consistent direction using efficient array scanning and hash lookup techniques.

array hash table two pointers

Problem Statement

You are given a circular array of non-zero integers nums, where each element nums[i] indicates the number of steps to move from index i, forward if positive and backward if negative. The array is circular, so moving past the last index wraps around to the first, and moving before the first wraps to the last index.

A valid cycle in this array consists of a sequence of indices seq with length greater than 1, where all elements in the sequence move consistently in one direction, either all forward or all backward. Your task is to determine if such a loop exists in nums.

Examples

Example 1

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

Output: true

The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward. We can see the cycle 0 --> 2 --> 3 --> 0 --> ..., and all of its nodes are white (jumping in the same direction).

Example 2

Input: nums = [-1,-2,-3,-4,-5,6]

Output: false

The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward. The only cycle is of size 1, so we return false.

Example 3

Input: nums = [1,-1,5,1,4]

Output: true

The graph shows how the indices are connected. White nodes are jumping forward, while red is jumping backward. We can see the cycle 0 --> 1 --> 0 --> ..., and while it is of size > 1, it has a node jumping forward and a node jumping backward, so it is not a cycle. We can see the cycle 3 --> 4 --> 3 --> ..., and all of its nodes are white (jumping in the same direction).

Constraints

1 <= nums.length <= 5000
-1000 <= nums[i] <= 1000
nums[i] != 0

Solution Approach

Hash-Based Direction Tracking

Use a hash or marker array to track visited indices and the direction of movement. For each unvisited index, traverse following nums[i], marking visited nodes. If you revisit a node with the same direction and length >1, a valid cycle exists.

Two-Pointer Cycle Detection

Apply slow and fast pointers starting from each unvisited index. Move slow by one step and fast by two steps according to nums[i]. If they meet and all steps follow the same direction, a cycle is confirmed. Reset nodes that break direction or form size 1 loops.

Optimization by Early Termination

Skip indices that have already been confirmed not part of any valid loop. When traversing, terminate immediately if the movement changes direction or reaches a single-length cycle, reducing redundant work and ensuring O(n) efficiency.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each index is visited at most twice by slow and fast pointers or hash markers. Space complexity is O(n) for the hash/visited array, though it can be reduced to O(1) using in-place marking strategies without altering the array.

What Interviewers Usually Probe

Asks about cycle detection with consistent direction in circular arrays
Questions about using fast/slow pointers versus hash arrays
Tests edge cases like single-length loops and direction changes

Common Pitfalls or Variants

Common pitfalls

Failing to handle single-element loops, which are invalid
Mixing forward and backward steps in the same cycle
Not accounting for array wrap-around properly when calculating next index

Follow-up variants

Allowing zero elements as valid steps, changing cycle conditions
Finding the longest valid loop instead of any loop
Detecting multiple non-overlapping cycles in the same array

FAQ

What is a Circular Array Loop problem?

It requires detecting a cycle in a circular array where all steps follow the same direction, forward or backward, of length greater than one.

Can a loop contain both forward and backward movements?

No, a valid loop must have all moves in a consistent direction; mixing forward and backward steps invalidates the cycle.

How does the hash lookup pattern help in this problem?

It allows tracking visited indices and directions efficiently, preventing redundant traversal and detecting cycles in O(n) time.

Why are single-element loops invalid?

A loop of size one does not meet the requirement of length greater than one, even if the index points to itself.

What techniques are recommended to solve this efficiently?

Combining array scanning with two-pointer cycle detection and hash-based direction tracking ensures fast and accurate identification of valid loops.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def circularArrayLoop(self, nums: List[int]) -> bool:
        n = len(nums)

        def next(i):
            return (i + nums[i] % n + n) % n

        for i in range(n):
            if nums[i] == 0:
                continue
            slow, fast = i, next(i)
            while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:
                if slow == fast:
                    if slow != next(slow):
                        return True
                    break
                slow, fast = next(slow), next(next(fast))
            j = i
            while nums[j] * nums[next(j)] > 0:
                nums[j] = 0
                j = next(j)
        return False

Continue Practicing

#522 longest uncommon subsequence ii #532 k diff pairs in an array #350 intersection of two arrays ii