target: 4
Given an array where each element is the maximum jump length from that position, decide whether you can reach the last index — a classic greedy problem where tracking the farthest reachable index at each step is both simpler and faster than DP.
You stand at index 0 of array nums. nums[i] is the maximum number of steps you may jump forward from index i. Return true if you can reach the last index, false if there is an unbridgeable gap.
Example: nums = [2,3,1,1,4]. From index 0 (jump 2) you reach index 1 or 2; from 1 (jump 3) you leap to index 4 — the last index. Answer: true.
Counter-example: nums = [3,2,1,0,4]. Every path reaches index 3, but nums[3]=0 traps you. Answer: false.
maxReach = the farthest index reachable from any position seen so far. At each index i, if i > maxReach there is a gap — you can never get here, so return false. Otherwise update maxReach = max(maxReach, i + nums[i]). If maxReach ever reaches or exceeds the last index, return true. You never need to simulate individual paths.maxReach = 0 (can only reach index 0 to start).i > maxReach — gap detected. Return false immediately (we can never land here).maxReach = max(maxReach, i + nums[i]). This captures the best jump from any reachable position so far.maxReach ≥ nums.length - 1, we've already covered the end — return true early.nums[i] === 0 as the failure condition. That's wrong — a zero jump at index i is fine if you can skip over it from an earlier jump. The only real failure is i > maxReach.dp[i] = reachable? Inner scan of all prior positions. Correct, but slow.The DP answer for dp[i] only depends on whether any earlier index can reach it — exactly what maxReach aggregates. The greedy collapses the entire DP table into one variable.
maxReach = 0. We scan left to right and track the farthest index we can reach.function canJump(nums: number[]): boolean {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false; // gap — can't get here
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true; // already past the end
}
return true; // all indices covered
}maxReach = 0 means the only index we know we can stand on is index 0. Everything else is unreachable until proven otherwise.i > maxReach, there is a hole between the last reachable index and i — no combination of prior jumps can bridge it. Return false immediately.i + nums[i] is the farthest we can reach from this position. Taking the max against the current maxReach ensures we never lose a previously established frontier.maxReach reaches or passes the last index we can stop — no need to process the remaining elements.0 to n-1 was reachable.maxReach integer is maintained. The greedy is strictly better than the O(n²) DP in both dimensions.maxReachsweep but track the current jump's boundary and increment a jump counter each time you cross it. Still O(n) / O(1).prev[] array during a DP backward scan (or BFS), then reconstruct by following prev from the end.true. First element zero with more elements is false. All zeros except last element is false (unless length is 1).| "can you reach the end / last index" | greedy maxReach scan |
| each element = max jump from that position | i + nums[i] frontier update |
| gap detection in a range-cover problem | i > maxReach → false |
| interval / coverage sweep | same maxReach pattern, count boundaries crossed |
function canJump(nums: number[]): boolean {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}nums = [2,3,1,1,4]. After visiting index 1 (value 3), what is maxReach?nums = [3,2,1,0,4]. Which condition triggers the false return?[2,3,1,1,4]? (Jump Game II)