Jump Game II
mediumGreedy+20 XPTime limit 2s
From index i you may jump forward by up to a[i] positions. Starting at index 0, what is the minimum number of jumps to reach the last index? (It is always reachable.)
Input:
- line 1:
n - line 2:
nnon-negative integers
Output: the minimum number of jumps.
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 1000; the last index is reachable.
Think about it: think in BFS "levels": all indices reachable with k jumps form a window. Scan it while tracking the farthest index reachable with one more jump; when you reach the end of the window, that's another jump. O(n), no queue needed.
Sample input 1
5 2 3 1 1 4
Sample output 1
2
Sample input 2
5 2 3 0 1 4
Sample output 2
2
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).