Circular Array Loop

Problem#

nums[i] says “jump that many steps (wrapping mod n)”. Return true if there exists a cycle satisfying: (1) length > 1, (2) all jumps in the cycle have the same sign.

Examples#

[2,-1,1,2,2] → true (0 → 2 → 3 → 0 is forward cycle of length 3)
[-1,-2,-3,-4,-5,6] → false (length-1 cycle disqualifies)

Constraints#

1 <= nums.length <= 5000.

Hints#

Hint 1

For each unvisited start, run fast/slow. Abort the walk on sign flip or self-loop.

Approach#

For each start i, do Floyd’s detection where the next-step function is (j + nums[j]) mod n (correctly handling negative mod). Reject the walk if the sign changes or if any step lands back on itself (length-1 cycle). To stay O(n) total, mark visited indices that don’t lead to a valid cycle so we never re-walk them.

Solution#

class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        const int n = nums.size();
        auto next = [&](int i) {
            int j = ((i + nums[i]) % n + n) % n;
            return j == i ? -1 : j;          // length-1 self-jump → invalid
        };
        for (int start = 0; start < n; ++start) {
            if (nums[start] == 0) continue;
            int slow = start, fast = start;
            int dir = nums[start];
            auto valid = [&](int i) {
                return i != -1 && ((long long)dir * nums[i] > 0);
            };
            while (true) {
                slow = next(slow);
                if (!valid(slow)) break;
                int f1 = next(fast);
                if (!valid(f1)) break;
                fast = next(f1);
                if (!valid(fast)) break;
                if (slow == fast) return true;
            }
        }
        return false;
    }
};

func circularArrayLoop(nums []int) bool {
    n := len(nums)
    next := func(i int) int {
        j := ((i+nums[i])%n + n) % n
        if j == i {
            return -1
        }
        return j
    }
    for start := 0; start < n; start++ {
        if nums[start] == 0 {
            continue
        }
        slow, fast := start, start
        dir := nums[start]
        valid := func(i int) bool {
            return i != -1 && int64(dir)*int64(nums[i]) > 0
        }
        for {
            slow = next(slow)
            if !valid(slow) {
                break
            }
            f1 := next(fast)
            if !valid(f1) {
                break
            }
            fast = next(f1)
            if !valid(fast) {
                break
            }
            if slow == fast {
                return true
            }
        }
    }
    return false
}

from typing import List

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

        def nxt(i: int) -> int:
            j = (i + nums[i]) % n
            return -1 if j == i else j

        for start in range(n):
            if nums[start] == 0:
                continue
            slow = fast = start
            direction = nums[start]

            def valid(i: int) -> bool:
                return i != -1 and direction * nums[i] > 0

            while True:
                slow = nxt(slow)
                if not valid(slow):
                    break
                f1 = nxt(fast)
                if not valid(f1):
                    break
                fast = nxt(f1)
                if not valid(fast):
                    break
                if slow == fast:
                    return True
        return False

var circularArrayLoop = function(nums) {
    const n = nums.length;
    const nxt = (i) => {
        const j = ((i + nums[i]) % n + n) % n;
        return j === i ? -1 : j;
    };
    for (let start = 0; start < n; start++) {
        if (nums[start] === 0) continue;
        let slow = start, fast = start;
        const dir = nums[start];
        const valid = (i) => i !== -1 && dir * nums[i] > 0;
        while (true) {
            slow = nxt(slow);
            if (!valid(slow)) break;
            const f1 = nxt(fast);
            if (!valid(f1)) break;
            fast = nxt(f1);
            if (!valid(fast)) break;
            if (slow === fast) return true;
        }
    }
    return false;
};

class Solution {
    private int[] nums;
    private int n;

    public boolean circularArrayLoop(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        for (int start = 0; start < n; start++) {
            if (nums[start] == 0) continue;
            int slow = start, fast = start;
            int dir = nums[start];
            while (true) {
                slow = next(slow);
                if (!valid(slow, dir)) break;
                int f1 = next(fast);
                if (!valid(f1, dir)) break;
                fast = next(f1);
                if (!valid(fast, dir)) break;
                if (slow == fast) return true;
            }
        }
        return false;
    }

    private int next(int i) {
        int j = ((i + nums[i]) % n + n) % n;
        return j == i ? -1 : j;
    }

    private boolean valid(int i, int dir) {
        return i != -1 && (long) dir * nums[i] > 0;
    }
}

function circularArrayLoop(nums: number[]): boolean {
    const n = nums.length;
    const nxt = (i: number): number => {
        const j = ((i + nums[i]) % n + n) % n;
        return j === i ? -1 : j;
    };
    for (let start = 0; start < n; start++) {
        if (nums[start] === 0) continue;
        let slow = start, fast = start;
        const dir = nums[start];
        const valid = (i: number): boolean => i !== -1 && dir * nums[i] > 0;
        while (true) {
            slow = nxt(slow);
            if (!valid(slow)) break;
            const f1 = nxt(fast);
            if (!valid(f1)) break;
            fast = nxt(f1);
            if (!valid(fast)) break;
            if (slow === fast) return true;
        }
    }
    return false;
}

Editorial#

Two pruning rules keep the algorithm clean: (a) once we see any sign change, no valid cycle starts here so abort; (b) the modulo formula ((x % n) + n) % n is the standard “true mod” for negative x in C++. The classical optimization marks visited nodes with 0 once we know the walk is dead, dropping the total work to O(n); the version above is O(n²) worst-case but the more readable one for interviews.

Complexity#

Time: O(n²) in the simple version; O(n) with marking.
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#