Use a greedy BFS-style scan: maintain the farthest index reachable and the boundary of the current jump level.

Jump Game II

hard

Acceptance: 37%

GreedyArrays

Starting at the first element of an integer array, reach the last element using the minimum number of jumps. From index i you may jump forward by up to nums[i] positions. It is guaranteed that the last index is always reachable.

Examples

Example 1:

Input:nums = [1,3,2,1,4]

Output:2

Example 2:

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

Output:2

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Jump Game II

Examples

Hints

Related Problems