Single Cycle Check

Tags

Single Cycle Check

Category

Graphs

Difficulty

Medium

Problem Statement

Given an array of integers where each element represents the number of steps to jump forward (positive) or backward (negative) from that index, determine whether following the jumps from index 0 forms a single cycle that visits every element exactly once and returns to the starting index.

Intuition

Starting at index 0, we follow the jumps for exactly n steps (where n is the length of the array). For a single cycle to exist, two conditions must be met: (1) after n jumps we must return to index 0, and (2) we must not return to index 0 before completing all n jumps (otherwise we have a shorter cycle that does not cover all elements).

Approach

  1. Start at index 0 with a counter for the number of elements visited.
  2. For n iterations:
    • Jump to the next index: currentIndex = (currentIndex + array[currentIndex]) % n.
    • Handle negative modulo to ensure the index wraps correctly.
    • Increment the visited counter.
    • If we are back at index 0 but have not visited all elements, return false (shorter cycle detected).
  3. After n jumps, check if we are back at index 0. If yes, return true; otherwise, false.

Pseudocode

function hasSingleCycle(array):
    n = length(array)
    currentIndex = 0
    numVisited = 0

    while numVisited < n:
        if numVisited > 0 and currentIndex == 0:
            return false
        numVisited++
        currentIndex = (currentIndex + array[currentIndex]) % n
        // Fix negative modulo
        if currentIndex < 0:
            currentIndex += n

    return currentIndex == 0

Time & Space Complexity

  • Time: O(n) where n is the length of the array. We perform exactly n jumps.
  • Space: O(1) — no additional data structures are used.

Key Insights

  • We do not need a "visited" array. The two conditions (visit all n elements, end at index 0) are sufficient.
  • If we return to index 0 early, it means some elements form a separate cycle and are unreachable.
  • Negative modulo can produce negative indices in some languages — always handle this with a correction step.
  • Jump values can be larger than the array length, so modular arithmetic is essential.

Edge Cases

  • Single-element array [0]: forms a trivial single cycle (jump 0 stays at index 0). Actually, this depends on interpretation — jumping 0 steps stays in place, so after 1 jump we are at index 0. This is a valid single cycle.
  • Array where all elements are 1 (or all -1): forms a single cycle.
  • Array with a 0 somewhere other than the start: if reached, the cycle gets stuck, so it cannot be a single cycle (unless the array has length 1).
  • Large positive or negative jump values that wrap around multiple times.

Linked mentions