Problem Description

You have a circular array of non-zero integers where each element tells you how many positions to jump from that index. Positive values mean jump forward, negative values mean jump backward. Since the array is circular, jumping past the end brings you to the beginning, and jumping before the start brings you to the end.

Your task is to determine if there exists a valid cycle in this array. A valid cycle must meet three conditions:

1. It forms a loop: Starting from some index, following the jump instructions repeatedly must eventually return you to the starting index
2. Consistent direction: All jumps in the cycle must be in the same direction (either all forward with positive values or all backward with negative values)
3. Multiple elements: The cycle must contain more than one element (you can't have a cycle that just loops on itself)

For example, if nums[i] = 3, you jump 3 positions forward from index i. If nums[i] = -2, you jump 2 positions backward from index i.

The function should return true if at least one valid cycle exists anywhere in the array, false otherwise.

The solution uses a two-pointer approach (slow and fast pointers) to detect cycles, similar to Floyd's cycle detection algorithm. It checks each potential starting position, uses the two pointers to find if a cycle exists, and validates that the cycle meets all requirements. Once a path is explored, it marks those positions with 0 to avoid redundant checking.

Intuition

The key insight is recognizing that this is fundamentally a cycle detection problem in a directed graph where each index points to exactly one other index. This immediately brings to mind Floyd's cycle detection algorithm (the "tortoise and hare" approach).

Think of the array as a graph where each index is a node, and each element creates a directed edge to another node based on the jump value. Since each node has exactly one outgoing edge, any path we follow will either eventually cycle or terminate (which can't happen here since every element is non-zero and always points somewhere).

The challenge is that not all cycles are valid. We need cycles where:

• All jumps go in the same direction (all positive or all negative values)
• The cycle has more than one element (no self-loops)

This suggests a strategy: for each starting position, we can use two pointers moving at different speeds. If they meet, we've found a cycle. But we need additional checks:

• While moving the pointers, we verify that consecutive jumps maintain the same sign (positive or negative)
• When we find a cycle, we check it's not a self-loop by ensuring slow != next(slow)

An optimization comes from realizing that once we've explored a path and determined it doesn't lead to a valid cycle, we never need to check any element on that path again as a starting point. Why? Because if starting from any point in that path could lead to a valid cycle, we would have already found it. So we can mark visited elements with 0 to skip them in future iterations.

The modulo arithmetic (i + nums[i] % n + n) % n handles the circular nature of the array, ensuring we wrap around correctly for both positive and negative jumps.

Solution Approach

The implementation uses Floyd's cycle detection algorithm with additional validations for the specific requirements of this problem.

Core Components:

1. Next Position Calculation:

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

   This helper function calculates the next index from position i. The formula (i + nums[i] % n + n) % n handles both positive and negative jumps while ensuring the result stays within bounds [0, n-1]. The % n on nums[i] prevents overflow, and adding n before the final modulo handles negative values correctly.

2. Main Loop - Testing Each Starting Position:

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

   We iterate through each index as a potential starting point. Skip indices marked as 0 (already processed).

3. Two-Pointer Cycle Detection:

   slow, fast = i, next(i)
   while nums[slow] * nums[fast] > 0 and nums[slow] * nums[next(fast)] > 0:

   • Initialize slow at the current index and fast one step ahead
   • The condition nums[slow] * nums[fast] > 0 ensures both pointers are in regions with the same sign (both positive or both negative)
   • The condition nums[slow] * nums[next(fast)] > 0 pre-checks that fast's next position also maintains the same sign
   • If signs differ, the path cannot form a valid cycle

4. Cycle Validation:

   if slow == fast:
       if slow != next(slow):
           return True
       break
   slow, fast = next(slow), next(next(fast))

   • When pointers meet (slow == fast), we've detected a cycle
   • Check slow != next(slow) to ensure it's not a self-loop (cycle length > 1)
   • If valid, return True
   • Otherwise, move slow one step and fast two steps for the next iteration

5. Path Marking Optimization:

   j = i
   while nums[j] * nums[next(j)] > 0:
       nums[j] = 0
       j = next(j)

   After exploring a path from index i that doesn't lead to a valid cycle, mark all elements in that path with 0. This prevents redundant checking since:

   • If a valid cycle existed in this path, we would have found it
   • Any future path entering this marked path won't find a valid cycle either

The algorithm efficiently finds cycles in O(n) time per starting position, but with the marking optimization, each element is visited at most once across all iterations, giving an overall O(n) time complexity and O(1) extra space.

Example Walkthrough

Let's walk through the algorithm with the array nums = [2, -1, 1, 2, 2].

Initial Setup:

• Array length n = 5
• We'll check each index as a potential starting point

Starting from index 0 (value = 2):

1. Initialize: slow = 0, fast = next(0) = (0 + 2) % 5 = 2
2. Check direction consistency:
   • nums[0] * nums[2] = 2 * 1 = 2 > 0 ✓ (same sign)
   • nums[0] * nums[next(2)] = 2 * nums[3] = 2 * 2 = 4 > 0 ✓
3. Move pointers: slow = next(0) = 2, fast = next(next(2)) = next(3) = 0
4. Check direction consistency:
   • nums[2] * nums[0] = 1 * 2 = 2 > 0 ✓
   • nums[2] * nums[next(0)] = 1 * nums[2] = 1 * 1 = 1 > 0 ✓
5. Move pointers: slow = next(2) = 3, fast = next(next(0)) = next(2) = 3
6. Pointers meet! slow == fast = 3
7. Check if it's not a self-loop: next(3) = (3 + 2) % 5 = 0 ≠ 3 ✓
8. Valid cycle found! The cycle is: 0 → 2 → 3 → 0

The cycle 0 → 2 → 3 → 0 is valid because:

• It forms a loop (returns to starting point)
• All values are positive (consistent direction)
• It contains 3 elements (more than one)

What if we had started from index 1 (value = -1)?

1. Initialize: slow = 1, fast = next(1) = (1 + (-1) + 5) % 5 = 0
2. Check direction consistency:
   • nums[1] * nums[0] = -1 * 2 = -2 < 0 ✗ (different signs)
3. Direction changes, so no valid cycle from this path
4. Mark path: Set nums[1] = 0 to avoid rechecking

Example of invalid self-loop: Consider if we had nums = [1, 2, 3, 4, -1] and started from index 4:

• next(4) = (4 + (-1) + 5) % 5 = 8 % 5 = 3
• Following the path: 4 → 3 → 2 → 0 → 1 → 3 (cycle detected at 3)
• But this mixes positive and negative values, so it would fail the direction check

The algorithm efficiently identifies the valid cycle while avoiding unnecessary rechecks through path marking.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm uses a two-pointer (slow and fast) approach to detect cycles. For each starting position i:

• The inner while loop runs at most O(n) times before either finding a cycle or breaking when the direction changes
• After processing each starting position, we mark visited elements as 0 to avoid reprocessing them
• The marking phase (second inner while loop) also runs at most O(n) times total across all iterations

Since each element is visited and processed at most twice (once in cycle detection and once in marking), and we have n starting positions, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm modifies the input array in-place by setting visited elements to 0, but doesn't use any additional data structures that scale with input size. Only a constant amount of extra space is used for variables like slow, fast, i, j, and n.

Common Pitfalls

1. Incorrect Modulo Operation for Negative Numbers

The Pitfall: When calculating the next position with negative jumps, a naive implementation might write:

def get_next_index(current_index: int) -> int:
    return (current_index + nums[current_index]) % n

This fails for negative jumps because in Python, -1 % 5 = 4, but -6 % 5 = 4 as well. However, if nums[current_index] is a large negative number like -10 at index 2 in an array of size 5, we get (2 + (-10)) % 5 = -8 % 5 = 2, which incorrectly suggests we stay at the same position.

The Solution: Always add n before taking the final modulo to ensure positive results:

def get_next_index(current_index: int) -> int:
    return (current_index + nums[current_index] % n + n) % n

The % n on nums[current_index] first normalizes large jumps, then adding n ensures the result is positive before the final modulo.

2. Forgetting to Check Fast Pointer's Next Position

The Pitfall: Only checking if nums[slow] * nums[fast] > 0 without verifying nums[next(fast)]:

# Incorrect - might move fast into opposite direction
while nums[slow_pointer] * nums[fast_pointer] > 0:
    # ... rest of the code

This could cause the fast pointer to jump into a region with opposite sign values in its next move, violating the consistent direction requirement.

The Solution: Always pre-check the fast pointer's next position to ensure it maintains the same direction:

while (nums[slow_pointer] * nums[fast_pointer] > 0 and 
       nums[slow_pointer] * nums[get_next_index(fast_pointer)] > 0):

3. Not Handling Self-Loops Correctly

The Pitfall: Accepting any cycle without verifying its length:

if slow_pointer == fast_pointer:
    return True  # Wrong! Could be a self-loop

An element that jumps to itself (e.g., nums[2] = 3 in an array of size 3) would be incorrectly identified as a valid cycle.

The Solution: Explicitly check that the cycle contains more than one element:

if slow_pointer == fast_pointer:
    if slow_pointer != get_next_index(slow_pointer):
        return True

4. Inefficient Path Marking

The Pitfall: Not marking explored paths or marking them incorrectly:

# Forgetting to mark visited paths
for start_index in range(n):
    # ... cycle detection logic
    # No marking of visited elements

This causes the algorithm to repeatedly check paths that have already been determined to not contain valid cycles, degrading performance to O(n²).

The Solution: Mark all elements in an invalid path with 0 after exploration:

current_position = start_index
while nums[current_position] * nums[get_next_index(current_position)] > 0:
    next_pos = get_next_index(current_position)
    nums[current_position] = 0  # Mark as visited
    current_position = next_pos

5. Array Modification Side Effects

The Pitfall: The solution modifies the input array by setting visited elements to 0. This might be unexpected behavior if the caller needs the original array preserved.

The Solution: If preserving the original array is required, create a separate visited array:

visited = [False] * n
# Use visited[i] instead of checking nums[i] == 0
# Mark with visited[i] = True instead of nums[i] = 0

Or make a copy of the array at the beginning if space complexity O(n) is acceptable.