LeetCode 457 - Circular Array Loop

LeetCode Problem 457

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers

Solution

Problem Understanding

This problem asks us to determine whether a circular array contains a valid cycle under a specific movement rule. Each element in the array represents how far we move from the current index. Positive numbers move forward, negative numbers move backward, and movement wraps around because the array is circular.

The key requirement is that a valid cycle must satisfy two conditions:

1. Every movement in the cycle must go in the same direction. All values must either be positive or all negative.
2. The cycle length must be greater than one. A single element pointing to itself does not count.

The input array nums contains non zero integers. Since the array is circular, moving past the last index wraps back to the beginning, and moving before index 0 wraps to the end.

For example, in the array [2, -1, 1, 2, 2]:

• Starting at index 0, move 2 steps to index 2
• From index 2, move 1 step to index 3
• From index 3, move 2 steps to index 0

This creates the cycle 0 -> 2 -> 3 -> 0, and every value involved is positive, so the answer is true.

The constraints are important:

• nums.length <= 5000
• Values are between -1000 and 1000
• No value is zero

The follow up asks for O(n) time and O(1) extra space, which strongly suggests we should avoid repeatedly revisiting the same indices and avoid using extra data structures like hash sets for every traversal.

Several edge cases are important:

• A self loop such as index i pointing back to itself is invalid because cycle length must exceed one.
• A path that changes direction midway is invalid.
• Arrays containing only one element can never contain a valid cycle.
• Large jump values must still wrap correctly using modular arithmetic.
• Negative modulo handling must be implemented carefully.

Approaches

Brute Force Approach

The brute force strategy is to try every index as a starting point and simulate movement step by step.

For each starting index:

1. Keep track of visited indices for this traversal.
2. Determine the required direction from the starting value.
3. Continue moving while:

• The direction remains consistent
• We have not revisited an index

4. If we revisit an index already seen in this traversal, check whether the cycle length is greater than one.

This approach works because it explicitly explores every reachable path and validates all cycle conditions.

However, it is inefficient because many traversals repeatedly visit the same indices. In the worst case, each starting position may traverse nearly the entire array.

This leads to O(n²) time complexity.

Optimal Approach

The optimal solution uses Floyd's Cycle Detection Algorithm, also known as the tortoise and hare technique.

The important insight is that the array can be viewed as a directed graph where each index points to exactly one next index.

Cycle detection naturally fits Floyd's algorithm:

• A slow pointer moves one step at a time
• A fast pointer moves two steps at a time
• If they meet, a cycle exists

However, we must add extra validation because not every graph cycle is valid for this problem.

We must ensure:

1. All movements remain in the same direction
2. The cycle length is greater than one

To achieve O(n) complexity overall, we also mark explored paths as visited by setting traversed elements to 0. Since the input guarantees no original value is zero, zero becomes a safe marker indicating that the index has already been processed and cannot contribute to a valid cycle.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Simulates traversal from every index using a visited set
Optimal	O(n)	O(1)	Uses Floyd cycle detection with in place marking

Algorithm Walkthrough

1. Iterate through every index in the array.

Each index could potentially belong to a valid cycle, so we must examine all unprocessed positions. 2. Skip indices already marked as 0.

We use 0 as a marker for indices already proven incapable of forming a valid cycle. Since original values are never zero, this is safe. 3. Determine the movement direction.

If nums[i] > 0, the traversal direction is forward. Otherwise, it is backward. 4. Initialize slow and fast pointers.

Both pointers begin at the current starting index. 5. Advance the pointers while movement remains valid.

A movement is valid only if:

• The next index maintains the same direction
• The traversal does not encounter a zero marker

The slow pointer advances one step.

The fast pointer advances two steps. 6. Check whether slow and fast pointers meet.

If they meet, a cycle may exist. 7. Reject self loops.

If the next index from the meeting point is the same index itself, then the cycle length is one, which is invalid. 8. Return true if a valid cycle is found.

Once a non trivial same direction cycle is detected, the problem is solved. 9. Mark the traversal path as visited if no valid cycle exists.

Starting from the current index, continue following the path while direction remains consistent, setting each visited element to 0.

This ensures future traversals do not repeat the same work. 10. Continue until all indices are processed.

If no valid cycle is found after processing the entire array, return false.

Why it works

Floyd's algorithm guarantees that if a cycle exists in a directed graph, slow and fast pointers will eventually meet. The additional direction checks ensure that only cycles with consistent movement direction are considered valid. The self loop check excludes cycles of length one. Finally, marking failed paths as zero guarantees that every index is processed at most once, which ensures linear time complexity.

Python Solution

from typing import List

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

        def next_index(current: int) -> int:
            return (current + nums[current]) % n

        for i in range(n):
            if nums[i] == 0:
                continue

            direction = nums[i] > 0

            slow = i
            fast = i

            while True:
                next_slow = next_index(slow)

                if nums[next_slow] == 0 or (nums[next_slow] > 0) != direction:
                    break

                next_fast = next_index(fast)

                if nums[next_fast] == 0 or (nums[next_fast] > 0) != direction:
                    break

                next_fast = next_index(next_fast)

                if nums[next_fast] == 0 or (nums[next_fast] > 0) != direction:
                    break

                slow = next_slow
                fast = next_fast

                if slow == fast:
                    if slow == next_index(slow):
                        break

                    return True

            current = i

            while nums[current] != 0 and (nums[current] > 0) == direction:
                next_pos = next_index(current)
                nums[current] = 0
                current = next_pos

        return False

The implementation begins by defining a helper function next_index, which computes the next position while correctly handling circular wrapping using modulo arithmetic.

The main loop iterates through every index. If an index has already been marked as 0, it is skipped because it has already been fully processed.

For each unprocessed index, the algorithm determines the traversal direction from the sign of the current value.

The slow and fast pointers are then initialized. Inside the loop, both pointers move only if direction consistency is maintained. This prevents invalid mixed direction cycles from being considered.

When the slow and fast pointers meet, the algorithm checks whether the cycle length is greater than one. A self loop is rejected by verifying whether the next index equals the current index.

If no valid cycle is found from the current start, the traversal path is cleaned up by marking all reachable same direction nodes as 0. This prevents repeated work and guarantees linear runtime.

Go Solution

func circularArrayLoop(nums []int) bool {
	n := len(nums)

	nextIndex := func(current int) int {
		return ((current + nums[current]) % n + n) % n
	}

	for i := 0; i < n; i++ {
		if nums[i] == 0 {
			continue
		}

		direction := nums[i] > 0

		slow := i
		fast := i

		for {
			nextSlow := nextIndex(slow)

			if nums[nextSlow] == 0 || (nums[nextSlow] > 0) != direction {
				break
			}

			nextFast := nextIndex(fast)

			if nums[nextFast] == 0 || (nums[nextFast] > 0) != direction {
				break
			}

			nextFast = nextIndex(nextFast)

			if nums[nextFast] == 0 || (nums[nextFast] > 0) != direction {
				break
			}

			slow = nextSlow
			fast = nextFast

			if slow == fast {
				if slow == nextIndex(slow) {
					break
				}

				return true
			}
		}

		current := i

		for nums[current] != 0 && (nums[current] > 0) == direction {
			nextPos := nextIndex(current)
			nums[current] = 0
			current = nextPos
		}
	}

	return false
}

The Go implementation closely mirrors the Python solution. One important difference is modulo handling. Go can produce negative modulo results, so the expression:

((current + nums[current]) % n + n) % n

ensures the final index is always non negative.

Go slices are used directly, and no extra memory structures are allocated, preserving the O(1) space requirement.

Worked Examples

Example 1

Input:

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

Initial State

Index	Value
0	2
1	-1
2	1
3	2
4	2

Start at index 0.

Direction is positive.

Step	Slow	Fast	Explanation
Initial	0	0	Both start at index 0
1	2	3	Slow moves once, fast moves twice
2	3	2	Continue moving
3	0	0	Pointers meet

Now check whether this is a self loop.

next_index(0) = 2

Since the next index differs from the current index, the cycle length exceeds one.

Return true.

Example 2

Input:

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

Traversal

Starting at index 0:

Step	Slow	Fast
Initial	0	0
1	5	4
2	5	5

Pointers meet at index 5.

Check self loop:

next_index(5) = 5

This is a cycle of length one, which is invalid.

The algorithm marks the explored path as zero and continues searching.

No valid cycle exists.

Return false.

Example 3

Input:

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

Starting at index 0:

Step	Slow	Fast	Notes
Initial	0	0	Direction positive
1	1	0	Fast pointer encounters direction mismatch

This path is invalid because direction changes.

Now start at index 3.

Step	Slow	Fast
Initial	3	3
1	4	3
2	3	3

Pointers meet.

Check self loop:

next_index(3) = 4

Not a self loop.

Return true.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is processed and marked at most once
Space	O(1)	Only a few pointers and variables are used

Although Floyd's cycle detection may appear nested, the cleanup phase guarantees that every index becomes zero after being processed unsuccessfully. Therefore, no index is revisited excessively, and the total work across all traversals remains linear.

Test Cases

from typing import List

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

        def next_index(current: int) -> int:
            return (current + nums[current]) % n

        for i in range(n):
            if nums[i] == 0:
                continue

            direction = nums[i] > 0

            slow = i
            fast = i

            while True:
                next_slow = next_index(slow)

                if nums[next_slow] == 0 or (nums[next_slow] > 0) != direction:
                    break

                next_fast = next_index(fast)

                if nums[next_fast] == 0 or (nums[next_fast] > 0) != direction:
                    break

                next_fast = next_index(next_fast)

                if nums[next_fast] == 0 or (nums[next_fast] > 0) != direction:
                    break

                slow = next_slow
                fast = next_fast

                if slow == fast:
                    if slow == next_index(slow):
                        break

                    return True

            current = i

            while nums[current] != 0 and (nums[current] > 0) == direction:
                next_pos = next_index(current)
                nums[current] = 0
                current = next_pos

        return False

solver = Solution()

assert solver.circularArrayLoop([2, -1, 1, 2, 2]) is True  # Valid positive cycle
assert solver.circularArrayLoop([-1, -2, -3, -4, -5, 6]) is False  # Self loop only
assert solver.circularArrayLoop([1, -1, 5, 1, 4]) is True  # Mixed invalid cycle plus valid cycle
assert solver.circularArrayLoop([1]) is False  # Single element self loop
assert solver.circularArrayLoop([1, 1, 1, 1]) is True  # Entire array forms cycle
assert solver.circularArrayLoop([-1, -1, -1]) is True  # Negative direction cycle
assert solver.circularArrayLoop([2, 2, -1, 2]) is True  # Positive cycle exists
assert solver.circularArrayLoop([1, -1]) is False  # Direction changes immediately
assert solver.circularArrayLoop([3, 1, 2]) is True  # Wrapping cycle
assert solver.circularArrayLoop([-2, 1, -1, -2, -2]) is False  # Direction mismatch prevents cycle

Test Summary

Test	Why
[2, -1, 1, 2, 2]	Standard valid cycle example
[-1, -2, -3, -4, -5, 6]	Self loop should be rejected
[1, -1, 5, 1, 4]	Mixed directions plus valid cycle
[1]	Single element edge case
[1, 1, 1, 1]	Entire array forms one cycle
[-1, -1, -1]	Valid negative cycle
[2, 2, -1, 2]	Cycle exists despite unrelated negative value
[1, -1]	Immediate direction conflict
[3, 1, 2]	Large jumps with wrapping
[-2, 1, -1, -2, -2]	Invalid because of direction inconsistency

Edge Cases

Self Loops

A major source of bugs is treating a single index pointing to itself as a valid cycle. For example:

[1]

Index 0 moves back to itself immediately. Although this technically forms a cycle in graph theory, the problem explicitly requires cycle length greater than one.

The implementation handles this with:

if slow == next_index(slow):
    break

This rejects all self loops.

Direction Changes

Another tricky case occurs when movement direction changes inside a traversal.

For example:

[1, -1]

Index 0 moves forward to index 1, but index 1 moves backward. This violates the same direction requirement.

The implementation validates direction before every pointer movement:

(nums[next_index] > 0) == direction

If the sign changes, traversal immediately stops.

Large Circular Wraps

Large jumps may wrap around the array multiple times.

For example:

[7, 1, 1, 1, 1]

Since the array length is 5, moving 7 steps effectively means moving 2 steps.

The implementation safely handles wrapping using modulo arithmetic:

(current + nums[current]) % n

This guarantees the next index always remains within valid bounds.