1.4 Jump Game I

Given an array A of non-negative integers, you are initially positioned at index 0 of the array. A[i] means the maximum jump distance from that position (you can only jump towards the end of the array). Determine if you are able to reach the last index.

Assumption: The given array is not null and length >= 1

Input: int[] array

Output: boolean if you can reach the last index from index 0 of the array

Solution 1:

1. Base case: dp[array.length - 1] = true

2. Induction rule: dp[i] represents whether we could reach the end index from index i. There exists 0<= j < i, to the left of j, all positions are reachable, and i is reachable from j → j + input[j] >= i

TC: O(array.length ^ 2)

SC: O(array.length)

public boolean canJump(int[] array) {
  if (array.length == 1) {
    return true;
  }
  boolean[] dp = new boolean[array.length];
  dp[0] = true;
  for (int i = 1; i < array.length; i++) {
    for (int j = 0; j < i; j++) {
      if (dp[j] && i <= j + array[j]) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[array.length - 1];
}

Solution 2:

1. To optimize Solution 1, maintain an index representing the last reachable position, initialized at array.length - 1, move from right to left until one unreachable position

2. Greedy solution, hard to follow up

TC: O(array.length)

SC: O(1)

public boolean canJump(int[] array) { 
  int lastPos = array.length - 1;
  for (int i = array.length - 1; i >= 0; i--) {
    if (array[i] + i >= lastPos) {
     lastPos = i;
    }
  }
  return lastPos == 0;
 }