[LeetCode] 45. Jump Game II

Posted on | In

Problem

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.

Example:

1
2
3
4
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.

Explanation

  1. If the input nums has length less than or equal to 1, we return 0 immediately.

  2. We need to create variable step to represent how many jump, farthest to represent the farthest index we can jump, end to represent current jump’s ending index. All these variables are initialized to 0.

  3. Loop through the input array from index 0 to len(nums) - 2 inclusive, in every iteration, we update the fartheset = max(farthest, i + nums[i]). If current index hits the end, that means we need to jump, so step += 1 and update end to be the farthest we have seen.

  4. Outside the loop, which means i hits the last index, we can return step as the result.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length <= 1) return 0;
        int step = 0;
        int farthest = 0;
        int end = 0;

        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == end) {
                step += 1;
                end = farthest;
            }
        }

        return step;
    }
}