Each number is the maximum jump length from that position. Starting at index 0, decide whether you can reach the last index.
DSA Animator › DSA Revision › Greedy › Jump Game
Remember: track only the farthest reachable index. If you ever stand beyond it, you are stuck. The video solves Jump Game (LeetCode 55, Medium) with the Greedy Reach pattern from the Greedy topic, and you can replay every step in the interactive Jump Game animation.
Each number is the maximum jump length from that position. Starting at index 0, decide whether you can reach the last index.
For 2, 3, 1, 1, 4, the answer is true. For 3, 2, 1, 0, 4, every path gets stuck at the 0, so the answer is false.
Trying every possible jump from every index explodes, and even dynamic programming is O of n squared. We only need to know the farthest index we can reach.
Keep a variable, far, for the farthest reachable index so far. At each index, if i is beyond far, we are stuck, so return false. Otherwise update far with i plus the jump length, and return true once far reaches the end.
At index 0, far becomes 0 plus 2, which is 2. At index 1, far becomes 1 plus 3, which is 4. That already reaches the last index, so the answer is true. In the second array, far stays at 3, and index 4 is beyond it, so the answer is false.
In code, loop over every index. If i is greater than far, return false. Update far, and return true after the loop, so it's O of n time and O of 1 space.
Remember: track only the farthest reachable index. If you ever stand beyond it, you are stuck.