> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0045-jump-game-ii.md).

# 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](https://leetcode.com/problems/jump-game-ii/discuss/18014/Concise-O%28n%29-one-loop-JAVA-solution-based-on-Greedy)

```java
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.