Circular Array Loop

Explanation & Solution

Description

You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:

If nums[i] is positive, move nums[i] steps forward
If nums[i] is negative, move |nums[i]| steps backward

Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backward from the first element puts you on the last element.

A cycle in the array consists of a sequence of indices seq of length k where:

Following the movement rules above results in a repeating index sequence: seq[0] → seq[1] → ... → seq[k-1] → seq[0] → ...
Every nums[seq[j]] is either all positive or all negative (the cycle must move in one consistent direction)
k > 1 (the cycle length must be greater than 1)

Return true if there is a cycle in nums, or false otherwise.

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

-1

Output: true

Explanation: There is a cycle: index 0 → 2 → 3 → 0. The cycle length is 3 and all values at these indices (2, 1, 2) are positive.

Constraints

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

Approach

Fast and Slow Pointers pattern

1. Define a Helper: getNext

Given index i, compute the next index: ((i + nums[i]) % n + n) % n
The double modulo with addition handles negative indices correctly for circular wrapping

2. Iterate Over Each Starting Index

For each index i, attempt to find a cycle starting from that index
Skip indices that have been marked as 0 (already proven to be dead ends)

3. Use Slow/Fast Pointers (Floyd's Algorithm)

Initialize slow = i and fast = i
Move slow one step at a time and fast two steps at a time
At each step, verify that the direction remains consistent: nums[current] * nums[i] > 0
If the direction changes, this path cannot form a valid cycle — break out

4. Check for Valid Cycle

If slow === fast, the pointers have met — a cycle is detected
Verify the cycle length is greater than 1: if slow === getNext(slow), it's a self-loop (length 1), which doesn't count
If the cycle is valid (length > 1, consistent direction), return true

5. Mark Dead-End Paths

If no valid cycle was found from index i, mark all indices along this path as 0
This prevents revisiting paths that are known dead ends, optimizing performance

6. Return Result

If no valid cycle is found after checking all starting indices, return false

Key Insight

Floyd's cycle detection is applied to an implicit graph defined by the circular array
The direction constraint (all positive or all negative) ensures the cycle moves consistently one way
The length > 1 constraint eliminates trivial self-loops
Marking visited paths as 0 gives an overall O(n) time complexity

Space

O(1)only pointer variables are used (the input array is modified in-place for marking)

Visualization

Input:

[2, -1, 1, 2, 2]

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

6 steps

Solution Code

Find the Duplicate Number

Linked List Components