Each number is the maximum jump length from that position, and the end is always reachable. Return the minimum number of jumps to reach the last index.
DSA Animator › DSA Revision › Greedy › Jump Game II
Remember: each jump is one window, like a level in BFS. Jump only when the current window runs out. The video solves Jump Game II (LeetCode 45, Medium) with the Greedy BFS Levels pattern from the Greedy topic, and you can replay every step in the interactive Jump Game II animation.
Each number is the maximum jump length from that position, and the end is always reachable. Return the minimum number of jumps to reach the last index.
For 2, 3, 1, 1, 4, the answer is 2. Jump from index 0 to index 1, then from index 1 to the end.
Trying every jump sequence is exponential, and dynamic programming is O of n squared. A greedy scan does it in one pass.
Think of it as levels: every index reachable with the same number of jumps forms one window. While scanning the current window, track the farthest index the next jump could reach. When you reach the end of the window, count a jump, and the next window ends at that farthest point.
The first window is just index 0, and from there far is 2. At the end of the window, jump once, and the next window ends at 2. Scanning indexes 1 and 2, far grows to 4. At index 2, the window ends, so jump again, and the new end, 4, is the last index. The answer is 2 jumps.
In code, loop i from 0 to n minus 2. Update far with i plus the jump length. When i equals the current end, add a jump and set end to far. It's O of n time and O of 1 space.
Remember: each jump is one window, like a level in BFS. Jump only when the current window runs out.