Jump Game

greedyarray

Problem

Given an array of non-negative integers nums, you start at the first index. Each element represents the maximum jump length from that position. Return true if you can reach the last index, false otherwise.

Examples

Example 1

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

Output: true

Explanation: Jump 1 step to index 1, then 3 steps to the last index.

Example 2

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

Output: false

Explanation: You always land on index 3, whose max jump is 0 — index 4 is unreachable.

Constraints

•1 <= nums.length <= 10^4
•0 <= nums[i] <= 10^5

Hints

Hint 1

A DP formulation works: reachable[i] is true if some earlier reachable[j] can jump far enough to reach i — but this checks many (i, j) pairs, O(n^2).

Hint 2

You don't actually need to know EVERY reachable index individually — only the single FARTHEST index reachable so far.

Hint 3

If the current index ever exceeds the farthest-reachable mark accumulated from all earlier positions, it's provably unreachable — stop immediately.

Solutions

public boolean canJumpDP(int[] nums) {
    boolean[] reachable = new boolean[nums.length];
    reachable[0] = true;
    for (int i = 0; i < nums.length; i++) {
        if (!reachable[i]) continue;
        for (int step = 1; step <= nums[i] && i + step < nums.length; step++) {
            reachable[i + step] = true;
        }
    }
    return reachable[nums.length - 1];
}

Time: O(n^2) worst case · Space: O(n)