Count Indices That Escape Array

Problem Overview

From each index you jump by exactly arr[i] steps, so every node has one outgoing edge and the structure is a functional graph.

Intuition

From each index you jump by exactly arr[i] steps, so every node has one outgoing edge and the structure is a functional graph. An index is good when following those jumps eventually leaves the array bounds, and bad when the walk hits a zero jump or loops forever. Painting each node as visiting, good, or bad while walking means every edge is processed a constant number of times, and later starts that land on a painted node reuse that answer immediately.

Algorithm

1Keep a state array: 0 unknown, 1 visiting, 2 escapes, 3 trapped.
2For each start whose state is still unknown, walk forward, marking each new node as visiting.
3Stop when the next index is out of bounds (escape), the jump is 0, a visiting node appears again (cycle), or a painted node is reached.
4Rewalk from the start along nodes still marked visiting and paint them with the final state.
5Count how many indices end with state 2.

Example Walkthrough

Input: arr = [2, 1, -1, 0, 2]

1. Index 0 jumps to 2, then to 1, then to 2 again, which is a cycle, so those nodes are trapped.
2. Index 3 has jump 0, so it is trapped.
3. Index 4 jumps to 6, which is outside, so only index 4 escapes.

Output: 1

Common Pitfalls

• A zero jump is a dead end. It does not leave the array.
• Hitting a node still marked visiting means the current walk found a cycle.
• Negative jumps are allowed and escape when the index goes below 0.
• Storing the whole path in a list works but is unnecessary; rewalking the visiting chain paints the same nodes.

Count Indices That Escape Array.java

Java

// Approach: Each index has one outgoing jump, so the array is a functional
// graph. An index is good when following jumps leaves the array, and bad when
// it hits 0 or a cycle. Memoize each node as visiting, good, or bad while
// walking iteratively; when the walk ends, rewalk the visiting chain to paint
// the final state. Later starts that hit a painted node reuse it in O(1).
// Complexity: O(n) time, O(n) space.
class Solution {
    // 0 = unknown, 1 = visiting, 2 = escapes, 3 = trapped
    public int goodIndices(int[] arr) {
        int n = arr.length;
        int[] state = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (state[i] == 0)
                paint(i, arr, state);
            if (state[i] == 2)
                count++;
        }
        return count;
    }

    private void paint(int start, int[] arr, int[] state) {
        int curr = start;
        while (curr >= 0 && curr < arr.length) {
            if (state[curr] == 2) {
                mark(start, arr, state, 2);
                return;
            }
            if (state[curr] == 3 || state[curr] == 1) {
                mark(start, arr, state, 3);
                return;
            }
            state[curr] = 1;
            int jump = arr[curr];
            if (jump == 0) {
                mark(start, arr, state, 3);
                return;
            }
            curr += jump;
        }
        mark(start, arr, state, 2);
    }

    private void mark(int start, int[] arr, int[] state, int val) {
        int curr = start;
        while (curr >= 0 && curr < arr.length && state[curr] == 1) {
            int jump = arr[curr];
            state[curr] = val;
            curr += jump;
        }
    }
}

Was this solution helpful?