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
- 1 ≤ n ≤ 10^5
- 0 ≤ a[i] ≤ 10^5
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
- You don't need the exact path — only how far you can possibly get.
- 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");
}
}