0045. Jump Game II

https://leetcode.com/problems/jump-game-ii

Description

Given an array of non-negative integers nums, 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.

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

Example 1:

**Input:** nums = [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.

Example 2:

**Input:** nums = [2,3,0,1,4]
**Output:** 2

Constraints:

• 1 <= nums.length <= 104

• 0 <= nums[i] <= 1000

ac

https://leetcode.com/problems/jump-game-ii/discuss/18014/Concise-O(n)-one-loop-JAVA-solution-based-on-Greedy

class Solution {
    public int jump(int[] nums) {
        // edge cases
        if (nums.length == 1) return 0;

        int step = 0, currEnd = 0, currFarthest = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            currFarthest = Math.max(currFarthest, i + nums[i]); // how far we can reach at current step
            if (currFarthest >= n-1) return step+1; // we hit the end
            if (i == currEnd) { // we can at most reach here at current step, need one more jump
                currEnd = currFarthest;
                step++;
            }
        }

        return -1;
    }
}

This is an implicit bfs solution. i == curEnd means you visited all the items on the current level. Incrementing jumps++ is like incrementing the level you are on. And curEnd = curFarthest is like getting the queue size (level size) for the next level you are traversing.