Reference: EPI 5.4

## Problem

In this board game, a player has to try to advance through a sequence of positions. Each position has a nonnegative integer associated with it, representing the maximum you can advance from that position in one move.

Write a program which takes an array of $n$ integers, where

`A[i]`

denotes the maximum you can advance from index $i$, and returns whether it is possible to advance to the last index starting from the beginning of the array.

**Example:**

1 | // Reachable |

## Analysis

### Brute-Force

Try every possible solution to see if we can reach the end. For example, if we can move by $3$ steps, we would try to move by $1$, $2$, and $3$ steps.

If the last index is reachable, it returns `true`

immediately, which is the base case of the recursive function.

1 | // brute-force |

Imagine there is an input array like $A = [N - 1, N - 2, N - 3, \ldots, 1]$ and the length of the array is also $N$. Marked

I think it depends on the input array.

**Time:** $O(N^N)$**Space:** $O(1)$

### Start-End Overlap

Using the idea in CS 61B | Challenge Lab 8 | Flight Problem (HeapPQ), we can reduce the problem as the following illustration.

We can draw a line starting from $i$ and crossing $n + 1$ elements if `A[i] = n`

.

1 | // Reachable |

The problem is reduced to another problem: Whether the lines are overlapped. We go through the array. If there is an entry, `count[i] += 1`

; if there is an exit, `count[i] -= 1`

.

We can maintain an array `count`

that stores a value denoting the number of entries minus the number of exits.

Meanwhile, when we go through the array, we use a variable to store a value (we can called it `balance`

). If the `balance`

is less than $0$ before the last index, it means that there is gap between those lines.

In the examples above, we have this following illustration.

1 | // Reachable |

**Note:** We allow that when `i = n - 1`

(the last index) the `balance`

becomes $0$. Since we have already been at the last index, it is reachable.

1 | public static boolean canReachEnd(List<Integer> A) { |

**Time:** $O(N)$**Space:** $O(N)$ needs extra space.

### Furthest (Greedy)

As we iterate through the array, we track the array, we track the furthest index we know we can advance to. The furthest we can advance is `i + A[i]`

.

During the iteration, if the current index `i`

is larger than `furthestIndex`

, we stop because `i`

could not be reached. In other words, we only advance when `i <= furthestIndex`

.

**Note:** The other condition could be `i < n`

or `furthestIndex < n - 1`

. The latter one shows that we only advance when we cannot reach the last index.

1 | public static boolean canReachEnd(List<Integer> A) { |

**Time:** $O(N)$**Space:** $O(1)$

## Variant

Write a program to compute the minimum number of steps needed to advance to the last location. Marked