[LeetCode] 45. Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

Thought process:

Since we can assume that we can always reach the last index, we know that every index can be reached.

1. Sub-problem: reach any index in the minimum number of jumps.
2. Formula: f[i] = min(f[j]) + 1, where 0 <= j < i and j + jumps[j] >= i.
3. Initialization: f[0] = 0. We don't need to jump at all to reach the first index.
4. Answer: f[last index].

Here we can also be greedy. If indexes a and b can both jump to c and a < b, then we can ignore b after we found a, because the minimum number of jumps to a must be less than or equal to that of b.

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int jump(int[] nums) { int length = nums.length; int[] f = new int[length]; f[0] = 0; for (int i = 1; i < length; i++) { for (int j = 0; j < i; j++) { if (j + nums[j] >= i) { f[i] = f[j] + 1; break; } } } return f[length - 1]; } }

Time complexity: O(n^2). Worst case is an array filled with 1.

There is also a pure greedy solution to this problem. When we start at the first index, we can jump to any index that's less than or equal to nums[0]. That is our first jump. In all the indexes that we can jump to at the first jump, one of them has a maximum reach i + nums[i] that can let us jump the farthest. That's our second jump. So the idea is, for each jump we make, we select the one that gives us the maximum reach.

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

public class Solution { public int jump(int[] nums) { int min = 0; int reach = 0; int last = 0; for (int i = 0; i < nums.length; i++) { if (i > last) { min++; last = reach; } reach = Math.max(reach, i + nums[i]); } return min; } }

Time complexity: O(n).