Practice › Greedy
Jump Game II
Medium · Greedy · Asked at Amazon, Google, Microsoft, Adobe
From index i you can jump forward by at most a[i] positions. You start at index 0 and it is guaranteed that the last index is reachable. Print the minimum number of jumps to reach the last index.
Input
First line: n. Second line: n space-separated integers.
Output
The minimum number of jumps.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 1000
BFS in layers on the array: all indices reachable with k jumps form a range; the next range ends at the farthest point reachable from it.
Example 1
Input
5 2 3 1 1 4
Output
2
Example 2
Input
5 2 3 0 1 4
Output
2
Hints
- All positions reachable with k jumps form one contiguous range.
- Walk through the current range, tracking the farthest index reachable from it; when you reach the end of the range, you must jump — the new range ends at that farthest index.
Approach
Implicit BFS by layers. end marks the last index reachable with jumps jumps, and far is the farthest index reachable with one more. For i from 0 to n − 2: update far = max(far, i + a[i]); when i == end, increment jumps and set end = far. Stopping at n − 2 avoids counting a jump from the last index.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
int jumps = 0, end = 0, far = 0;
for (int i = 0; i < n - 1; i++) {
far = max(far, i + a[i]);
if (i == end) {
jumps++;
end = far;
}
}
cout << jumps << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1 : 1 + data[0]]
jumps = end = far = 0
for i in range(len(a) - 1):
far = max(far, i + a[i])
if i == end:
jumps += 1
end = far
print(jumps)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
int jumps = 0, end = 0, far = 0;
for (int i = 0; i < n - 1; i++) {
far = Math.max(far, i + a[i]);
if (i == end) {
jumps++;
end = far;
}
}
System.out.println(jumps);
}
}