Skip to content
AI360Xpert
Back to Greedy
Medium

Jump Game II

You are given a 0-indexed array of integers `nums` of length `n`. You are initially positioned at `nums[0]`. Each element `nums[i]` represents the maximum length of a forward jump from index `i`. In other words, if you are at `nums[i]`, you can jump to any `nums[i + j]` where: - `0 <= j <= nums[i]` and - `i + j < n` Return the minimum number of jumps to reach `nums[n - 1]`. The test cases are generated such that you can reach `nums[n - 1]`.

Examples

Input:nums = [2,3,1,1,4]
Output:2
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.
Input:nums = [2,3,0,1,4]
Output:2
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • It's guaranteed that you can reach nums[n - 1].

Greedy Approach (BFS Analogy)

Approach

We can think of this as an implicit Breadth-First Search (BFS). At each step, we keep track of the current window (range of indices) we can reach with the current number of jumps. We maintain two pointers: `left` and `right`. Initially, `left = 0` and `right = 0` (0 jumps). In each iteration, we examine all elements in the current window `[left, right]` and find the furthest index we can reach (`farthest = max(farthest, i + nums[i])`). Then, we update our window for the next jump: `left = right + 1` and `right = farthest`. We also increment our jump count. We stop when `right` reaches or exceeds the last index.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) because each element is visited at most once within the `for` loop. Space complexity is O(1) as we only use a few pointers and variables.

Solution.java
class Solution {    public int jump(int[] nums) {        int jumps = 0;        int left = 0;        int right = 0;                while (right < nums.length - 1) {            int farthest = 0;            for (int i = left; i <= right; i++) {                farthest = Math.max(farthest, i + nums[i]);            }            left = right + 1;            right = farthest;            jumps++;        }                return jumps;    }}