At each step take the choice that looks best right now and never revisit it. It works when a local best always leads to a global best.
Used for
reach = max(0, 0 + 2) = 2
reach = max(2, 1 + 3) = 4
Jumps are [1, 0, 2]. Can you reach the last cell?
Not quite. From cell 0 you reach cell 1. Cell 1 allows a jump of 0, so you can never get to cell 2.
Step 1 of 5
Goal: can you reach the last cell if each number is the farthest you may jump from that cell? Idea: only track the farthest cell you could possibly reach so far. Never try individual routes.
Step 2 of 5
At cell 0 you can jump up to 2, so the farthest reach is cell 2.
Step 3 of 5
Cell 1 is within reach. From there you can jump 3 cells: 1 + 3 = 4. The reach grows to the last cell.
Step 4 of 5
The last cell is reachable, so the answer is yes. We never followed a path: taking the best choice at each step (the farthest reach) is enough here, in one pass. Taking the locally best option like this is a greedy approach.
Step 5 of 5
Your turn.
Pascal's TriangleJump GameKruskal's AlgorithmPrim's Algorithm
function canJump(nums) { let reach = 0; for (let i = 0; i < nums.length; i++) { if (i > reach) return false; reach = Math.max(reach, i + nums[i]); } return true;}