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:

## 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.

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.

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.

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.

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.

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

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.
Info
Article :
50
Total Count :
82.3k
UV :
PV :
Last Push :