Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. All positions reachable with k jumps form one contiguous range.
  2. 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);
    }
}

Solve Jump Game II online · All practice problems