How to Find Good Indices in an Array Using DFS and Dynamic Programming

Problem Statement

Given an integer array arr[], each index tells us how many positions we should move from that index.

For an index i, the next index is calculated as:

next = i + arr[i];

The movement follows these rules:

If arr[i] is positive, we move to the right.
If arr[i] is negative, we move to the left.
If arr[i] is 0, we cannot move, so that index is bad.
If the movement goes outside the array, that index is good.
If the movement continues forever in a cycle, that index is bad.

We need to return the number of good indices.

Example

Consider the following array:

arr = [2, 3, -1, 2, -2, 4, 1]

Let's calculate the movement from different indices.

Index 0

0 → 2 → 1 → 4 → 2 → ...

The path enters a cycle:

2 → 1 → 4 → 2

Therefore, index 0 is bad.

Index 1

1 → 4 → 2 → 1 → ...

A cycle exists, so index 1 is bad.

Index 2

2 → 1 → 4 → 2 → ...

A cycle exists, so index 2 is bad.

Index 3

3 → 5 → 9

The array size is 7. Since 9 >= 7, we have moved outside the array.

Therefore, index 3 is good.

Index 5

5 → 9

We leave the array, so index 5 is good.

Index 6

6 → 7

We leave the array, so index 6 is good.

Therefore:

Good indices = 3, 5, 6
Answer = 3

Main Idea

This problem can be viewed as a directed graph.

Each array index is a node. From every index, there can be at most one outgoing edge:

i → i + arr[i]

For example, consider:

arr = [2, 3, -1, 2, -2, 4, 1]

The graph contains paths such as:

0 → 2
1 → 4
2 → 1
3 → 5
4 → 2
5 → outside
6 → outside

There are two possible outcomes.

Case 1: The Path Goes Outside the Array

3 → 5 → outside

This is a good index because the movement eventually leaves the array.

Case 2: The Path Enters a Cycle

1 → 4 → 2 → 1

This is a bad index because the movement never leaves the array.

The problem becomes determining whether the path starting from each index eventually reaches outside the array or enters a cycle.

DFS Approach

We can solve this problem using Depth-First Search (DFS), cycle detection, and dynamic programming.

For every index, we need to remember whether it is good or bad. We also need to detect cycles during traversal.

For this, we use two arrays:

int[] state;
boolean[] good;

The state array tracks the progress of DFS, while the good array stores the final result for each index.

Understanding the State Array

The state array has three possible values:

state[i] = 0 → Not visited
state[i] = 1 → Currently visiting
state[i] = 2 → Completely processed

State 0: Not Visited

We have not started processing this index.

state[i] = 0

State 1: Currently Visiting

The index is part of the current DFS path.

For example:

0 → 2 → 1 → 4
          ↑
      processing

If we reach an index whose state is already 1, we have found a cycle in the current DFS path.

State 2: Completely Processed

We already know the result for this index.

We can reuse the stored result instead of processing the same path again. This is where memoization helps avoid repeated work.

state[i] = 2

Why Do We Need the Good Array?

The state[] array tells us whether an index has been visited or processed. It does not, by itself, tell us whether the index is good.

For example:

good[3] = true;

This means index 3 eventually escapes the array.

Similarly:

good[2] = false;

This means index 2 eventually reaches a cycle or a position where movement stops.

The good[] array stores the final result for each index.

DFS Logic

For an index i, we first calculate the next index:

int next = index + arr[index];

Then we handle the following cases.

Case 1: The Index Is Outside the Array

if (index < 0 || index >= arr.length) {
    return true;
}

The path has escaped the array, so it is good.

Case 2: The Current Value Is Zero

if (arr[index] == 0) {
    state[index] = 2;
    good[index] = false;
    return false;
}

When arr[index] is zero, we cannot move anywhere. Therefore, the index is bad.

Case 3: The Index Is Already Processed

if (state[index] == 2) {
    return good[index];
}

We have already calculated the answer for this index, so we return the stored result.

This avoids unnecessary repeated traversal.

Case 4: A Cycle Is Detected

if (state[index] == 1) {
    return false;
}

The index is already present in the current DFS path. Reaching it again means a cycle exists.

For example:

2 → 1 → 4 → 2

Therefore, we return false.

Complete Java Code

class Solution {

    public int goodIndices(int[] arr) {

        int n = arr.length;

        // 0 = unvisited
        // 1 = currently visiting
        // 2 = completely processed
        int[] state = new int[n];

        // Stores whether each index can escape
        boolean[] good = new boolean[n];

        int count = 0;

        for (int i = 0; i < n; i++) {

            if (dfs(i, arr, state, good)) {
                count++;
            }
        }

        return count;
    }

    private boolean dfs(int index, int[] arr,
                        int[] state, boolean[] good) {

        // Case 1: We escaped from the array
        if (index < 0 || index >= arr.length) {
            return true;
        }

        // Case 2: Zero means no movement
        if (arr[index] == 0) {
            state[index] = 2;
            good[index] = false;
            return false;
        }

        // Case 3: Already processed
        if (state[index] == 2) {
            return good[index];
        }

        // Case 4: Cycle detected
        if (state[index] == 1) {
            return false;
        }

        // Mark current index as visiting
        state[index] = 1;

        // Calculate the next index
        int next = index + arr[index];

        // Check whether the next path can escape
        boolean canEscape = dfs(next, arr, state, good);

        // Mark current index as completely processed
        state[index] = 2;

        // Store the result
        good[index] = canEscape;

        return canEscape;
    }
}

Dry Run

Consider the array:

arr = [2, 3, -1, 2, -2, 4, 1]

Processing Index 0

Start with index 0.

Calculate the next index:

next = 0 + 2 = 2

The path becomes:

0 → 2

Now process index 2:

2 + (-1) = 1

The path becomes:

0 → 2 → 1

Process index 1:

1 + 3 = 4

The path becomes:

0 → 2 → 1 → 4

Process index 4:

4 + (-2) = 2

The path becomes:

0 → 2 → 1 → 4 → 2

Index 2 is already being visited, so state[2] == 1. We have found a cycle:

2 → 1 → 4 → 2

Therefore, indices 4, 1, 2, and 0 are all bad.

Processing Index 3

Now consider index 3.

3 + 2 = 5

The path becomes:

3 → 5

At index 5:

5 + 4 = 9

The array size is 7. Since 9 >= 7, we have escaped the array.

Therefore:

good[5] = true
good[3] = true

Processing Index 6

Now consider index 6.

6 + 1 = 7

Since 7 >= 7, we leave the array.

Therefore:

good[6] = true

Final Result

Index	Result
0	Bad
1	Bad
2	Bad
3	Good
4	Bad
5	Good
6	Good

The good indices are 3, 5, and 6.

Answer = 3

Why Is the Time Complexity O(n)?

At first glance, DFS might appear to revisit the same indices repeatedly. However, once an index is completely processed, its result is stored:

state[index] = 2;

Later, if another path reaches that index, the algorithm returns the stored result:

return good[index];

It does not traverse the same path again.

Each index is therefore processed only a constant number of times, and each index has at most one outgoing edge.

The total time complexity is:

O(n)

Space Complexity

The algorithm uses three sources of auxiliary space:

state[]     → O(n)
good[]      → O(n)
DFS stack   → O(n) in the worst case

Therefore, the overall auxiliary space complexity is:

O(n)

Important Concepts Used

This problem combines several important concepts.

1. Graph

Every index is treated as a node, and the array value determines the next node.

i → i + arr[i]

2. Depth-First Search

DFS follows the jump path from the current index until it reaches an exit, a cycle, or an already processed index.

3. Cycle Detection

The condition state[index] == 1 tells us that the current DFS path has returned to an active node.

4. Dynamic Programming

Once an index has been processed, its result is saved in good[index] and reused whenever another path reaches it.

5. Memoization

Memoization prevents the algorithm from solving the same path repeatedly. Combined with cycle detection, it allows the solution to process the graph efficiently.

Common Mistakes

Mistake 1: Only Checking Whether the Path Leaves the Array

Checking only the next index is not enough:

if (next >= n || next < 0)

The path can enter a cycle instead of leaving the array.

For example:

0 → 2 → 1 → 4 → 2

The algorithm must detect cycles as well.

Mistake 2: Treating Zero as a Good Index

When:

arr[i] == 0

the movement stops at the current index. According to the problem statement, this index is bad.

Mistake 3: Using Only a Visited Array

A simple boolean[] visited cannot distinguish between an index currently being processed and one that has already been completely processed.

That distinction is necessary for correct cycle detection.

Use three states instead:

0 → Unvisited
1 → Currently visiting
2 → Completely processed

Mistake 4: Recalculating Results for Processed Indices

Traversing the same paths repeatedly can increase the running time. Store the final result in good[] and reuse it when an index is already processed.

Summary

The Good Indices problem can be solved by modeling the array as a directed graph in which each index has at most one outgoing edge. DFS follows the movement from each index, while three-state cycle detection distinguishes active nodes from completely processed nodes. The good[] array stores whether each index eventually escapes the array, allowing previously calculated results to be reused. With memoization, each index is processed only a constant number of times, giving the solution a time complexity of O(n) and an auxiliary space complexity of O(n).