Check for a Loop in an Array of Jumps

Given an array arr of n integers, each element describes a jump from its index, wrapping around the ends:

a positive arr[i] moves forward: the next index is (i + arr[i]) % n,
a negative arr[i] moves backward by |arr[i]|, also wrapping around,
if arr[i] % n == 0, index i has no move.

Return true if following the jumps can form a loop that visits more than one index.

Example

Text

[2, -1, 1, 2, 2]  ->  true    (0 -> 2 -> 3 -> 0)
[1, 1, 1, 1, 1]   ->  true    (0 -> 1 -> 2 -> 3 -> 4 -> 0)
[1, 2]            ->  false   (0 -> 1, and index 1 has no move: 2 % 2 == 0)

Every index has at most one outgoing edge. A loop exists if walking from some index eventually comes back to an index already on the same walk.

next returns the index reached from i, or -1 when i has no move. Math.floorMod always returns a value in 0..n-1, so backward jumps that pass index 0 wrap to the end. Java's % keeps the sign of the left side (-1 % 5 is -1), which is why it isn't enough here. Values and sums are computed as long, so a large arr[i] can't overflow int.

Java

import java.util.Arrays;

public class Main {
    static int next(int[] arr, int i) {
        long n = arr.length;
        long step = arr[i] % n;
        if (step == 0) return -1;
        return (int) Math.floorMod(i + step, n);
    }

    public static void main(String[] args) {
        int[] arr = {2, -1, 1, 2, 2};
        int[] moves = new int[arr.length];
        for (int i = 0; i < arr.length; i++) moves[i] = next(arr, i);
        System.out.println(Arrays.toString(moves));
    }
}

Output

[2, 0, 3, 0, 1]

Brute force: walk n steps from every index

A walk that loops returns to its own start within n steps if the start is on the loop. Try every start.

Java

public class Main {
    static int next(int[] arr, int i) {
        long n = arr.length;
        long step = arr[i] % n;
        if (step == 0) return -1;
        return (int) Math.floorMod(i + step, n);
    }

    static boolean hasLoop(int[] arr) {
        for (int start = 0; start < arr.length; start++) {
            int cur = start;
            for (int steps = 0; steps < arr.length; steps++) {
                int j = next(arr, cur);
                if (j == -1) break;        // no move: this walk ends
                if (j == start) return true;
                cur = j;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasLoop(new int[]{2, -1, 1, 2, 2}) + " " + hasLoop(new int[]{1, 1, 1, 1, 1}) + " " + hasLoop(new int[]{1, 2}));
    }
}

Output

true true false

Time: O(n²). Space: O(1).

Optimal: one coloring pass

Give every index a color: unvisited, or the number of the walk that first reached it. Walk from each unvisited index, coloring as you go, and stop at an index that has no move or is already colored:

colored by this walk: the walk came back to itself, so there's a loop.
colored by an earlier walk: everything from there on was already explored and had no loop.

Every index is colored once, so the total work is linear. This is the same idea as the three-state cycle detection in a directed graph, simplified because each vertex has at most one edge.

walkOf[i] holds the number of the walk that colored index i, or -1 if no walk has reached it yet.

Java

import java.util.Arrays;

public class Main {
    static int next(int[] arr, int i) {
        long n = arr.length;
        long step = arr[i] % n;
        if (step == 0) return -1;
        return (int) Math.floorMod(i + step, n);
    }

    static boolean hasLoop(int[] arr) {
        int[] walkOf = new int[arr.length];
        Arrays.fill(walkOf, -1);
        for (int start = 0; start < arr.length; start++) {
            int cur = start;
            while (walkOf[cur] == -1) {
                walkOf[cur] = start;
                int j = next(arr, cur);
                if (j == -1) break;
                cur = j;
            }
            if (walkOf[cur] == start && next(arr, cur) != -1) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(hasLoop(new int[]{2, -1, 1, 2, 2}) + " " + hasLoop(new int[]{1, 1, 1, 1, 1}) + " " + hasLoop(new int[]{1, 2}));
        System.out.println(hasLoop(new int[]{-1, -1}) + " " + hasLoop(new int[]{3, 3, 3}));
    }
}

Output

true true false
true false

Time: O(n). Space: O(n) for the colors.

When the inner loop stops, either cur has no move, or cur was already colored. The final check tells these apart: a colored cur reached through a move from this walk means the walk closed a loop. In [3, 3, 3], every 3 % 3 == 0, so no index moves at all.

Edge cases

Self-loops: a jump that is a multiple of n returns to the same index, and the problem counts that as no move, so it can't form a loop.
LeetCode variant (457. Circular Array Loop): the loop must also move in one direction only. Stop a walk when the sign of arr[cur] changes.