Getting everything ready for you…

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

0s

Practice › Greedy

Jump Game

Medium · Greedy · Asked at Amazon, Microsoft, Google, Adobe

a[i] is the maximum jump length from index i. Starting at index 0, print YES if you can reach the last index, otherwise NO.

Input

First line: n. Second line: n non-negative integers.

Output

YES or NO.

Constraints

Track the farthest index reachable so far.

Example 1

Input

5
2 3 1 1 4

Output

YES

Example 2

Input

5
3 2 1 0 4

Output

NO

Hints

  1. You don't need the exact path — only how far you can possibly get.
  2. Track farthest = max(farthest, i + a[i]) while scanning. If you ever stand at an index i > farthest, you are stuck.

Approach

Scan left to right keeping farthest, the largest index reachable so far. If the current index is beyond farthest, it can't be reached, and nothing after it can be either, so answer NO. Otherwise extend farthest = max(farthest, i + a[i]). If the scan reaches the last index, answer YES.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long farthest = 0;
    bool ok = true;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (i > farthest) { ok = false; break; }
        farthest = max(farthest, i + x);
    }
    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
farthest, ok = 0, True
for i, x in enumerate(data[1 : data[0] + 1]):
    if i > farthest:
        ok = False
        break
    farthest = max(farthest, i + x)
print("YES" if ok else "NO")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long farthest = 0;
        boolean ok = true;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (i > farthest) { ok = false; break; }
            farthest = Math.max(farthest, i + x);
        }
        System.out.println(ok ? "YES" : "NO");
    }
}

Solve Jump Game online · All practice problems