Jump Game

Question (LC.55)

Given an array of non-negative integers, each element represents the max length you can jump at that position. Starting from the first index, can you reach the end?

Example

I: A = [2,3,1,1,4]
O: True
I: A = [3,2,1,0,4]
O: there is a 0 on the index 3 and no way to jump over it. False

Analysis

First thing to do is drawing out the jump DAG. Having a concrete picture is much easier way to think than looking at the numbers themselves. Essentially, we want to know whether there is a path from the first node to the last node. Intuitively, we can use DFS to test if the last node is reachable from the first node.

DFS Approach

public boolean canJump(int[] nums) {
    if (nums == null || nums.length == 0) {
        return true;
    }
    int[] flag = new int[1];
    jumpHelper(nums, 0, flag);
    return flag[0] == 1;
}

private void jumpHelper(int[] nums, int currentPos, int[] flag) {
    if (flag[0] == 1) {
    return;
    }
    if (currentPos == nums.length - 1) {
        flag[0] = 1;
        return;
    }
    for (int i = 1; i <= nums[currentPos]; i++) {
        jumpHelper(nums, currentPos + i, flag);
    }
}

DP Approach

Then we observe there can overlapping paths. For example, if we already know a path is not leading to the destination, we don't have to recursively visit it again.

5-->1-->2-->0-->0-->1
     memo[2]

1. Define (optimal) subproblem
Jump(i) = can you jump to index i from index 0

2. Solve by prefix
for j from i-1 to 0
    if Jump(j) and nums(j) >= i-j
        Jump(i) = true
        (we can break as long as we find one true Jump(j))

3. Init base
Jump(0) = true

4. Topo order
for i from 1 to n-1

5. Final answer
Jump(n-1)

DP Code

public boolean canJump(int[] nums) {
    // create memo
    int n = nums.length;
    boolean[] memo = new boolean[n];

    // init base
    memo[0] = true;

    // topo order
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i - 1; j >= 0; j--) {
            if (memo[j] && nums[j] >= i - j) {
                memo[i] = true;
                break;
            }
        }
    }

    // final answer
    return memo[n - 1];
}

Greedy Approach

Jump Game II (LC.45)

The objective now is to minimize the number of steps to reach the last index.

Example

I: nums = [2,3,1,1,4]
O: 2-->3-->4 = 2 jumps

What if there's a gap? For instance [2,1,0,0,5]. Assume that you can always reach the last index.

Analysis

Obviously, we can do an exhaustive search from the last index to find all possible paths and maintain a global min. But then many paths would be revisited many times. We can use memoization or tabulation to avoid recomputing the same path.

DP Approach

1. Optimal subproblem
    jp(i) = minimum number of jumps to reach index i
2. Solve by prefix
    for j from i to 0
        if reachable: jp(i) = Math.min(jp(i), jp(j) + 1)
3. Topo order
    for i from 1 to n-1
4. Base case
    all init to unreachable
    jp(0) = 1
5. Final answer
    jp(n-1)

DP Code

public int jump(int[] nums) {
    int n = nums.length;
    // create memo table
    int[] jp = new int[n];
    // init base case
    jp[0] = 0; // don't count the first jump
    for (int i = 1; i < n; i++) {
        jp[i] = Integer.MAX_VALUE;
    }
    // topo order
    for (int i = 1; i < n; i++) {
        // recurrence
        for (int j = i-1; j >= 0; j--) {
            if (nums[j] + j >= i) { // reachable
                jp[i] = Math.min(jp[i], jp[j] + 1);
            }
        }
    }    
    // final answer
    return jp[n-1];
}

Time & Space Complexity

The DP solution gives O(n^2) time and uses O(n) extra space. However, it results in time limit exceeded on LC. This begs for another approach that is linear time.

Greedy Approach

Exchange argument

1. Switch to the pos before and can jump to the current pos

2. Keep the rest of the solution optimal

3. Search backward from current pos to find the leftest pos that can jump to the current position then look left again from that leftest position

def jump(self, nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return 0
    
    current_index = n - 1
    steps = 0 

    while current_index > 0:
        for i in range(current_index - 1, -1, -1):
            if nums[i] + i >= current_index:
                left_most_index = i
        current_index = left_most_index
        steps += 1
    
    return steps 

Time O(n^2) Space O(1)

Conclusion

We can certainly use memoization for any DP question. But if the we can easily figure out the topological ordering, then we can also do tabulation which saves the call stack.