Sweep left to right, maintaining the farthest index reachable so far.

Jump Game

medium

Acceptance: 43%

Dynamic Programming

You stand at position zero of an integer array. Each entry tells you the farthest you may leap forward from that position. Determine whether it is possible to arrive at the final position of the array.

Examples

Example 1:

Input:nums = [3,1,2,0,4]

Output:true

Explanation: Leap from index 0 to index 2 (distance 2), then from index 2 to index 4 (distance 2).

Example 2:

Input:nums = [2,0,0,1,4]

Output:false

Explanation: No matter how you jump, you become stuck at index 2 whose value is 0.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Jump Game

Examples

Hints

Related Problems