Jump Game

mediumDynamic Programming+20 XPTime limit 2s

You start at index 0. From index i you may jump forward by up to a[i] positions. Can you reach the last index?

Input:

line 1: n
line 2: n non-negative integers

Output: true or false.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 10⁵.

Think about it: a DP over every jump is O(n²) in the worst case. Greedy is O(n): track the farthest index reachable so far; if you ever stand beyond it, you're stuck.

Sample input 1

5
2 3 1 1 4

Sample output 1

true

Sample input 2

5
3 2 1 0 4

Sample output 2

false

📖 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).

Loading editor…