EPI 5.4 | Advancing Through an Array

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:

// Reachable
     0  1  2  3  4  5  6
A = [3, 3, 1, 0, 2, 0, 1]
     ---- 1 step
        ---------- 3 steps
                 ------- 2 steps
// Non-Reachable
     0  1  2  3  4  5  6
A = [3, 2, 0, 0, 2, 0, 1]

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.

// brute-force
public static boolean canReachEnd(List<Integer> A) {
  return dfs(A, 0);
}

// dfs
private static boolean dfs(List<Integer> steps, int pos) {
  if (pos >= steps.size() - 1) {
    return true;
  }
  int numStep = steps.get(pos);
  for (int i = 1; i <= numStep; ++i) {
    if (dfs(steps, pos + i)) {
      return true;
    }
  }
  return false;
}

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.

// Reachable
     0  1  2  3  4  5  6
A = [3, 3, 1, 0, 2, 0, 1]
     ----------
        ----------
           ----
                 -------
                       ----
// Non-Reachable
     0  1  2  3  4  5  6
A = [3, 2, 0, 0, 2, 0, 1]
     ----------
        -------
                 -------
                       ----
               ^ // here is a gap, so the end is not 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.

// Reachable
     0  1  2  3  4  5  6
A = [3, 3, 1, 0, 2, 0, 1]
     ----------
        ----------
           ----
                 -------
                       ----
    +1 +1 +1 -1 -1    -1
             -1 +1    +1
Bal: 1  2  3  1  1  1  1

// Non-Reachable
     0  1  2  3  4  5  6
A = [3, 2, 0, 0, 2, 0, 1]
     ----------
        -------
                 -------
                       ----
    +1 +1    -1 +1    -1
             -1       +1
Bal: 1  2  2  0 // <- gap is detected

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.

public static boolean canReachEnd(List<Integer> A) {
  int n = A.size();
  int[] numStartExit = new int[n];
  int balance = 0;

  for (int i = 0; i < n; ++i) {
    // if (A.get(i) > 0) { // if A.get(i) == 0, do nothing
    int start = i;
    int end = start + A.get(i);
    numStartExit[start] += 1;
    if (end < n) {
      numStartExit[end] -= 1;
    }
    // } // the if can be removed (think about why~)
    balance += numStartExit[i];
    // check: not the last element && balance <= 0
    if (i < n - 1 && balance <= 0) {
      return false;
    }
  }
  return true;
}

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.

public static boolean canReachEnd(List<Integer> A) {
  int n = A.size();
  int lastIndex = n - 1;
  int furthestIndex = 0;
  for (int i = 0; i <= furthestIndex && furthestIndex < lastIndex; ++i) {
    furthestIndex = Math.max(furthestIndex, i + A.get(i));
  }
  return furthestIndex >= lastIndex;
}

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