Jump Game
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)