Circular Array Loop - Practice Coding Problems

Circular Array Loop - Problem

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 abs(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 backwards 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 the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k-1] -> seq[0] -> ...
Every nums[seq[j]] is either all positive or all negative
k > 1 (cycle must have more than one element)

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

Input & Output

Example 1 — Valid Cycle

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

› Output: true

💡 Note: There is a cycle: index 1 → index 0 → index 2 → index 0. All values in cycle have same direction (negative: -1, -2), and cycle length is 2 > 1.

Example 2 — No Valid Cycle

$ Input: nums = [-1,2]

› Output: false

💡 Note: Index 0 moves to index 1, index 1 moves to index 1 (self-loop). Self-loops are invalid since cycle length must be > 1.

Example 3 — Direction Change

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

› Output: false

💡 Note: No valid cycle exists because paths either lead to direction changes or form invalid cycles.

Constraints

1 ≤ nums.length ≤ 5000
-1000 ≤ nums[i] ≤ 1000
nums[i] ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array with movement instructions

Process

Follow paths and detect valid cycles

Output

Return true if valid cycle exists

Key Takeaway

🎯 Key Insight: Use Floyd's cycle detection with direction validation to find valid loops efficiently

Asked in

G Google 35 a Amazon 28 M Microsoft 22 A Apple 15

The key insight is to detect cycles in a circular array while ensuring direction consistency and cycle length > 1. Best approach uses Floyd's cycle detection with path marking optimization. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Path Marking	O(n)	O(n)	Mark visited nodes to avoid redundant checks and detect cycles efficiently
Brute Force - Check Every Starting Point	O(n²)	O(n)	Start from each index and follow the path until we find a cycle or determine no cycle exists
Floyd's Cycle Detection (Fast & Slow Pointers)	O(n²)	O(1)	Use fast and slow pointers to detect cycles efficiently, similar to detecting cycles in linked lists

Optimized with Path Marking — Algorithm Steps

Step 1: Mark current path nodes during traversal
Step 2: If we hit a marked node, check for valid cycle
Step 3: Mark completed paths to avoid reprocessing
Step 4: Validate cycle direction and length constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Path

Mark nodes as we traverse the path

Detect Cycle

If we hit a marked node, check for cycle

Skip Visited

Avoid reprocessing already checked paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int nextIndex(int* nums, int numsSize, int i) {
    return (i + nums[i] % numsSize + numsSize) % numsSize;
}

bool solution(int* nums, int numsSize) {
    bool* visited = (bool*)calloc(numsSize, sizeof(bool));
    
    for (int i = 0; i < numsSize; i++) {
        if (visited[i] || nums[i] == 0) continue;
        
        // Use slow and fast pointers for this path
        int slow = i, fast = i;
        bool forward = nums[i] > 0;
        
        // Check if we can form a valid cycle
        while ((nums[slow] > 0) == forward && 
               (nums[fast] > 0) == forward && 
               (nums[nextIndex(nums, numsSize, fast)] > 0) == forward) {
            slow = nextIndex(nums, numsSize, slow);
            fast = nextIndex(nums, numsSize, nextIndex(nums, numsSize, fast));
            
            if (slow == fast) {
                // Found potential cycle, check if length > 1
                if (slow == nextIndex(nums, numsSize, slow)) break; // Self loop
                free(visited);
                return true;
            }
        }
        
        // Mark all nodes in this path as visited
        int curr = i;
        while (!visited[curr] && (nums[curr] > 0) == forward) {
            visited[curr] = true;
            curr = nextIndex(nums, numsSize, curr);
        }
    }
    
    free(visited);
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    ptr++;
    
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, numsSize);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each node is visited at most twice due to marking optimization

✓ Linear Growth

Space Complexity

O(n)

Additional arrays to track node states during traversal

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Path Marking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler