Jump Game II

Jump Game II raises the bar. The first version only asked if you can reach the end. This one assumes you always can, and asks for the fewest jumps to get there. So now every jump has a cost. The slow way tries every option and counts. The fast way jumps in smart windows. That window idea is the whole trick.

🎯 The Problem

You get an array of numbers and must find the fewest jumps to land on the last position.

• Each number is the most steps you can jump forward from that position.
• You start at position 0.
• The end is always reachable. You are promised this.
• Return the smallest number of jumps to reach the last index.

Let us say the array is [2, 3, 1, 1, 4]. From position 0 you can jump up to 2 steps. The best move is to jump to position 1, because from there you can jump 3 steps straight to the end. So the answer is 2 jumps.

Input:  nums = [2, 3, 1, 1, 4]
Output: 2

Explanation: Jump 1 step from index 0 to index 1, then 3 steps to the last index.

The greedy partner here is the idea of a window. A window is the range of positions you can reach with the jumps you have spent so far. Here is the first window from index 0. With one jump you can land anywhere it covers.

🐢 Approach 1: Recursion (Brute Force)

Try every jump from every spot and keep the smallest count.

The idea:

• From position 0, try every reachable spot.
• From each of those, try again.
• Keep a running count of jumps. Take the smallest count that reaches the end.

Why it is weak:

• The recursion branches a lot. You revisit the same spots through different paths.
• The time grows huge, around O(2^n) in the worst case.

Here is the plain recursion code:

def jump(nums):
    def dfs(index):
        if index >= len(nums) - 1:
            return 0
        best = float("inf")
        for step in range(1, nums[index] + 1):
            best = min(best, 1 + dfs(index + step))
        return best

    return dfs(0)

⚡ Approach 2: Recursion With Memory (Better)

The idea in one line: store the fewest jumps from each spot once, then reuse it.

The idea:

• This is dynamic programming, which is recursion plus a memory of past answers.
• Each spot has a fixed answer: the fewest jumps from here to the end.
• Compute it once. Save it. Reuse it.

Why it is better:

• No spot is solved twice.
• Time drops to O(n²). For each spot you still scan all the spots it can reach.

Why it is still not best:

• It uses O(n) extra space for the memory.
• It still does O(n²) work. One pass can do the same job.

Here is the memoized recursion code:

from functools import lru_cache


def jump(nums):
    @lru_cache(None)
    def dfs(index):
        if index >= len(nums) - 1:
            return 0
        best = float("inf")
        for step in range(1, nums[index] + 1):
            best = min(best, 1 + dfs(index + step))
        return best

    return dfs(0)

🚀 Approach 3: Greedy Level Windows (Best)

The idea in one line: treat jumps as levels and stretch each level as far as it can go before spending the next jump.

The idea:

• Think of jumps as levels, like ripples spreading out.
• With one jump you can reach a whole range of indices. With two, a wider range.
• Each level is a window of reachable positions.

How it works:

• Sweep the array. Keep end, the end of the current window.
• Inside the window, track farthest, the best reach from any spot in it.
• When the index meets end, the window is used up. Add one to the jump count.
• Set end to farthest, opening the next window.

Why it is fast:

• One pass through the array. So it is O(n).
• Inside one window every spot costs the same jumps. So only reaching farther helps.
• Greedy means you keep the single farthest reach and trust it.

Here is a dry run on [2, 3, 1, 1, 4]. Watch the window end move and the jump count rise.

Steps to Solve

1. Start with jumps = 0, end = 0, and farthest = 0.
2. Walk through the array but stop before the last index. You do not jump from the goal.
3. At each spot, update farthest to the bigger of farthest and i + nums[i].
4. When i reaches end, you have used up the current window. Add one to jumps.
5. Set end to farthest, opening the next window.
6. After the loop, jumps holds the fewest jumps to reach the end.

#include <stdio.h>

int jump(int nums[], int n) {
    int jumps = 0;     // jumps used so far
    int end = 0;       // end of the current window
    int farthest = 0;  // farthest reach inside the window
    for (int i = 0; i < n - 1; i++) {   // never jump from the last index
        int far = i + nums[i];
        if (far > farthest) {
            farthest = far;             // best reach in this window
        }
        if (i == end) {                 // window finished
            jumps++;                    // spend a jump
            end = farthest;             // open the next window
        }
    }
    return jumps;
}

int main(void) {
    int nums[] = {2, 3, 1, 1, 4};
    int n = 5;
    printf("%d\n", jump(nums, n));
    return 0;
}

2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int jump(vector<int>& nums) {
    int jumps = 0, end = 0, farthest = 0;
    for (int i = 0; i < (int)nums.size() - 1; i++) {  // skip last index
        farthest = max(farthest, i + nums[i]);        // best reach
        if (i == end) {              // window finished
            jumps++;                 // spend a jump
            end = farthest;          // open next window
        }
    }
    return jumps;
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << jump(nums) << endl;
    return 0;
}

2

public class JumpGameII {
    public static int jump(int[] nums) {
        int jumps = 0, end = 0, farthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {  // skip last index
            farthest = Math.max(farthest, i + nums[i]);  // best reach
            if (i == end) {            // window finished
                jumps++;               // spend a jump
                end = farthest;        // open next window
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        int[] nums = { 2, 3, 1, 1, 4 };
        System.out.println(jump(nums));
    }
}

2

def jump(nums):
    jumps = 0      # jumps used so far
    end = 0        # end of the current window
    farthest = 0   # farthest reach inside the window
    for i in range(len(nums) - 1):     # never jump from the last index
        farthest = max(farthest, i + nums[i])  # best reach
        if i == end:                   # window finished
            jumps += 1                 # spend a jump
            end = farthest             # open the next window
    return jumps


nums = [2, 3, 1, 1, 4]
print(jump(nums))

2

function jump(nums) {
  let jumps = 0;     // jumps used so far
  let end = 0;       // end of the current window
  let farthest = 0;  // farthest reach inside the window
  for (let i = 0; i < nums.length - 1; i++) {  // skip last index
    farthest = Math.max(farthest, i + nums[i]); // best reach
    if (i === end) {            // window finished
      jumps++;                  // spend a jump
      end = farthest;           // open next window
    }
  }
  return jumps;
}

const nums = [2, 3, 1, 1, 4];
console.log(jump(nums));

2

Let us walk through the Python version line by line, because the window idea is easy to miss.

jumps = 0, end = 0, farthest = 0 set up the three numbers we need. jumps counts how many jumps we have spent. end is the last index of the current window. farthest is the best reach we have seen inside this window.

for i in range(len(nums) - 1): loops to the second-last index on purpose. We never jump from the goal itself. If we looped to the end we would count one jump too many.

farthest = max(farthest, i + nums[i]) stretches the window. From spot i we can reach i + nums[i]. We keep whichever reach is larger. This is the greedy core.

if i == end: is the window boundary. When the loop index meets the window end, we have used up everything one jump can reach. So we must spend another jump now.

jumps += 1 records that jump. end = farthest opens the next window, which stretches to the best reach we found.

return jumps gives the fewest jumps once the sweep is done.

⏱️ Time and Space Complexity

The recursion tries every path, so it is very slow. Adding memory turns it into dynamic programming, which still scans the reach of each spot. The greedy way keeps three numbers and one loop. So it trades nothing and still wins. That takes the time all the way down to O(n) with O(1) extra space.

🧩 Key Takeaways

• ✅ Think of jumps as levels, where each level is a window of reachable positions.
• ✅ Inside a window, only track the farthest reach. Every spot in it costs the same jumps.
• ✅ When the index meets the window end, spend a jump and open the next window.
• ✅ Loop to the second-last index, because you never jump from the goal.
• ✅ This runs in O(n) time with O(1) extra space, beating the O(n²) dynamic programming.

🚀 What’s Next?

• Jump Game
• Gas Station