Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Jump Game II

MEDIUMProblemSolveExternal Links

Description

You are given a 0-indexed array of integers nums of length n. You start at the first position (index 0).

Each element nums[i] tells you the maximum number of positions you can jump forward from index i. So if you are standing at index i, you may jump to any index from i + 1 up to i + nums[i], as long as the destination is within the bounds of the array.

Your goal is to reach the last index (n - 1) using the fewest number of jumps possible.

You are guaranteed that it is always possible to reach the last index.

In simpler terms: Imagine a row of stepping stones numbered 0 through n − 1. The number on each stone tells you the farthest stone you can leap to from where you are standing. Starting on stone 0, figure out the minimum number of leaps needed to land on the very last stone.

Examples

Example 1

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

Output: 2

Explanation: From index 0, you can jump 1 or 2 positions forward (because nums[0] = 2). Jump to index 1 (value 3). From index 1, you can jump up to 3 positions forward, reaching index 4 (the last index) in one more jump. Total jumps = 2.

Example 2

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

Output: 2

Explanation: Jump from index 0 to index 1 (value 3). From index 1, you can jump up to 3 positions forward, reaching index 4 directly. Even though index 2 has value 0 (a dead end), we bypass it by choosing a better landing spot. Total jumps = 2.

Example 3

Input: nums = [1]

Output: 0

Explanation: You are already at the last index. No jumps are needed.

Constraints

  • 1 ≤ nums.length ≤ 10^4
  • 0 ≤ nums[i] ≤ 1000
  • It is guaranteed that you can reach nums[n - 1].

Editorial

Brute Force

Intuition

The most natural way to think about this problem is: "From where I am standing, I can jump to several positions. Let me try every single possibility, and for each landing spot, repeat the same logic until I reach the end."

This is exactly the same reasoning you would use if you were physically standing on stepping stones and had unlimited time — try every path, remember how many jumps each path took, and pick the shortest one.

More precisely, from index i, you can jump to index i + 1, i + 2, ..., up to i + nums[i]. For each of those destinations, recursively find the minimum jumps to reach the end. The answer for index i is 1 + min(jumps from each reachable index).

This exhaustive exploration guarantees correctness because it evaluates every possible route. However, the number of routes grows explosively as the array gets larger.

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 1, 4]:

Step 1: Start at index 0 (value 2). We can jump to index 1 or index 2. Try both paths.

Step 2 — Path A: Jump to index 1 (value 3). From here we can jump to index 2, 3, or 4.

Step 3 — Path A → sub-path 1: Jump from index 1 to index 2 (value 1). From index 2 we can only reach index 3.

Step 4 — Path A → sub-path 1 → deeper: Jump from index 2 to index 3 (value 1). From index 3 we can reach index 4. That is the end! This path took 4 jumps total: 0→1→2→3→4.

Step 5 — Path A → sub-path 2: Jump from index 1 to index 3 (value 1). From index 3 we reach index 4. That is 3 jumps: 0→1→3→4.

Step 6 — Path A → sub-path 3: Jump from index 1 to index 4. We reached the end! That is 2 jumps: 0→1→4.

Step 7 — Path B: Jump from index 0 to index 2 (value 1). From index 2 we reach index 3, then index 4. That is 3 jumps: 0→2→3→4.

Step 8: Compare all completed paths: 4 jumps, 3 jumps, 2 jumps, 3 jumps. The minimum is 2.

Algorithm

  1. Define a recursive function minJumps(i) that returns the minimum jumps from index i to the last index.
  2. Base case: If i ≥ n - 1, return 0 (already at or past the end).
  3. Recursive case: For each reachable index j from i + 1 to i + nums[i] (within bounds), recursively compute minJumps(j).
  4. Return 1 + min(minJumps(j)) for all valid j.
  5. If no j can reach the end (all return infinity), return infinity for this index.
  6. The answer is minJumps(0).

Code

class Solution {
public:
    int jump(vector<int>& nums) {
        return minJumps(nums, 0);
    }

private:
    int minJumps(vector<int>& nums, int i) {
        int n = nums.size();
        if (i >= n - 1) return 0;

        int best = INT_MAX;
        for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
            int sub = minJumps(nums, j);
            if (sub != INT_MAX) {
                best = min(best, 1 + sub);
            }
        }
        return best;
    }
};
class Solution:
    def jump(self, nums: list[int]) -> int:
        n = len(nums)

        def min_jumps(i: int) -> int:
            if i >= n - 1:
                return 0
            best = float('inf')
            for j in range(i + 1, min(i + nums[i] + 1, n)):
                sub = min_jumps(j)
                if sub != float('inf'):
                    best = min(best, 1 + sub)
            return best

        return min_jumps(0)
class Solution {
    public int jump(int[] nums) {
        return minJumps(nums, 0);
    }

    private int minJumps(int[] nums, int i) {
        int n = nums.length;
        if (i >= n - 1) return 0;

        int best = Integer.MAX_VALUE;
        for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
            int sub = minJumps(nums, j);
            if (sub != Integer.MAX_VALUE) {
                best = Math.min(best, 1 + sub);
            }
        }
        return best;
    }
}

Complexity Analysis

Time Complexity: O(n^n) in the worst case. At each index, you can branch into up to nums[i] recursive calls, and this branching happens at every level of recursion. For an array of length n where each element is large, the call tree can be exponentially deep and wide.

Space Complexity: O(n) for the recursion call stack. In the deepest path, we make at most n recursive calls before hitting the base case.

Why This Approach Is Not Efficient

The brute-force recursion has exponential time complexity — O(n^n) — because it re-explores the same sub-problems repeatedly. For instance, minJumps(3) might be computed hundreds of times via different paths that all pass through index 3.

With the constraint n ≤ 10^4, an exponential algorithm will never finish within a reasonable time limit. Even for a small array of 20 elements, the number of recursive paths can exceed millions.

The key observation is that many calls overlap: the minimum jumps from index i to the end depends only on i, regardless of how we arrived at i. This is a classic signal for Dynamic Programming — we can store computed results and reuse them instead of re-computing from scratch.

Better Approach - Dynamic Programming

Intuition

Since the brute-force solution recalculates minJumps(i) many times for the same index, we can eliminate this redundancy by storing results.

Create an array dp where dp[i] holds the minimum number of jumps needed to reach the last index starting from index i. We fill this table from right to left:

  • dp[n-1] = 0 because we are already at the destination.
  • For every other index i, look at all positions reachable from i (indices i+1 through i + nums[i]), find the one with the smallest dp value, and set dp[i] = 1 + that minimum.

Think of it like planning a road trip backwards: you know exactly how many stops are needed from every gas station to the destination, so when you arrive at a new station, you just check which next station minimizes your total stops.

The answer is dp[0].

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 1, 4]:

Step 1: Initialize dp array of size 5 with infinity everywhere except dp[4] = 0.
dp = [∞, ∞, ∞, ∞, 0]

Step 2: Process i = 3. nums[3] = 1, so we can reach index 4. dp[4] = 0, so dp[3] = 1 + 0 = 1.
dp = [∞, ∞, ∞, 1, 0]

Step 3: Process i = 2. nums[2] = 1, so we can reach index 3. dp[3] = 1, so dp[2] = 1 + 1 = 2.
dp = [∞, ∞, 2, 1, 0]

Step 4: Process i = 1. nums[1] = 3, so we can reach indices 2, 3, 4. Their dp values are 2, 1, 0. The minimum is 0 (index 4). dp[1] = 1 + 0 = 1.
dp = [∞, 1, 2, 1, 0]

Step 5: Process i = 0. nums[0] = 2, so we can reach indices 1 and 2. Their dp values are 1 and 2. The minimum is 1 (index 1). dp[0] = 1 + 1 = 2.
dp = [2, 1, 2, 1, 0]

Step 6: The answer is dp[0] = 2.

Jump Game II — Bottom-Up DP Table Fill — Watch how the dp array fills from right to left. For each index, we check all reachable positions and pick the one with the fewest jumps to the end.

Algorithm

  1. Create an array dp of size n, initialized to infinity. Set dp[n-1] = 0.
  2. Iterate i from n - 2 down to 0.
  3. For each i, iterate j from i + 1 to min(i + nums[i], n - 1).
  4. If dp[j] is not infinity, update dp[i] = min(dp[i], 1 + dp[j]).
  5. After processing all indices, return dp[0].

Code

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                if (dp[j] != INT_MAX) {
                    dp[i] = min(dp[i], 1 + dp[j]);
                }
            }
        }
        return dp[0];
    }
};
class Solution:
    def jump(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [float('inf')] * n
        dp[n - 1] = 0

        for i in range(n - 2, -1, -1):
            for j in range(i + 1, min(i + nums[i] + 1, n)):
                if dp[j] != float('inf'):
                    dp[i] = min(dp[i], 1 + dp[j])

        return dp[0]
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[n - 1] = 0;

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j <= i + nums[i] && j < n; j++) {
                if (dp[j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], 1 + dp[j]);
                }
            }
        }
        return dp[0];
    }
}

Complexity Analysis

Time Complexity: O(n²). For each index i, the inner loop examines up to nums[i] subsequent indices. In the worst case (e.g., every element is n), the total work across all indices is proportional to n × n.

Space Complexity: O(n) for the dp array of size n.

Why This Approach Is Not Efficient

The DP solution correctly computes the answer, but its O(n²) time complexity becomes problematic for larger inputs. With n up to 10^4, the inner loop can perform up to 10^4 iterations for each of the 10^4 outer iterations, leading to roughly 10^8 operations in the worst case — right at the edge of typical time limits and often causing Time Limit Exceeded.

More importantly, the DP approach does redundant work. When filling dp[i], we scan all reachable indices and compare their dp values. But we do not need to know the exact dp value of every reachable index — we only care about whether we can extend our reach farther with one more jump.

This insight leads to a greedy approach: instead of computing minimum jumps for every single index, we can process indices left-to-right and greedily decide when to take a jump, always choosing the option that maximizes how far we can go next.

Optimal Approach - Greedy (BFS Layers)

Intuition

Think of the problem as a Breadth-First Search (BFS) on layers.

  • Layer 0 contains just the starting index.
  • Layer 1 contains all indices reachable from Layer 0 with exactly 1 jump.
  • Layer 2 contains all new indices reachable from Layer 1 with exactly 2 jumps.
  • And so on.

The first time the last index appears in some layer, that layer number is the answer.

Instead of using a queue (like standard BFS), we exploit the fact that reachable indices form a contiguous range. At any point, the current "layer" spans from some start to an end boundary (currentEnd). As we scan through that layer, we track the farthest index reachable from any position in the layer. When we finish scanning the layer (i.e., i reaches currentEnd), we take a jump, setting the new boundary to farthest.

Three variables are all we need:

  • jumps — how many jumps we have taken so far.
  • currentEnd — the rightmost index reachable without taking another jump (the boundary of the current layer).
  • farthest — the rightmost index reachable from any index within the current layer.

We scan left-to-right through the array. At each index i, we update farthest = max(farthest, i + nums[i]). When i reaches currentEnd, we must take a new jump: increment jumps and set currentEnd = farthest.

This greedy choice is optimal because within a layer, jumping to the position that yields the maximum reach guarantees the fewest layers (fewest jumps) to the end.

Step-by-Step Explanation

Let's trace through with nums = [2, 3, 1, 1, 4]:

Initialize: jumps = 0, currentEnd = 0, farthest = 0.

Step 1 (i = 0): Update farthest = max(0, 0 + 2) = 2. We reached the boundary (i == currentEnd == 0), so we must jump: jumps = 1, currentEnd = 2. Layer 1 covers indices 1..2.

Step 2 (i = 1): Update farthest = max(2, 1 + 3) = 4. We have not yet reached the boundary (i=1 < currentEnd=2), so keep scanning.

Step 3 (i = 2): Update farthest = max(4, 2 + 1) = 4. We reached the boundary (i == currentEnd == 2), so we must jump: jumps = 2, currentEnd = 4. Layer 2 covers indices 3..4.

Step 4 (i = 3): Update farthest = max(4, 3 + 1) = 4. We have not reached the boundary (i=3 < currentEnd=4). But since we only loop up to i = n - 2 = 3, the loop ends here.

Result: jumps = 2. The farthest reached is index 4 (the last index), confirming we can get there in 2 jumps.

Jump Game II — Greedy BFS Layer Scan — Watch the greedy algorithm scan left-to-right, tracking the farthest reachable index and jumping only when the current layer boundary is reached.

Algorithm

  1. Initialize three variables: jumps = 0, currentEnd = 0, farthest = 0.
  2. Iterate i from 0 to n - 2 (do not process the last index).
  3. At each i, update farthest = max(farthest, i + nums[i]).
  4. If i == currentEnd (we have reached the boundary of the current jump layer):
    • Increment jumps.
    • Set currentEnd = farthest (extend the boundary to the farthest reachable index).
  5. Return jumps.

Code

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int jumps = 0, currentEnd = 0, farthest = 0;

        for (int i = 0; i < n - 1; i++) {
            farthest = max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }
};
class Solution:
    def jump(self, nums: list[int]) -> int:
        n = len(nums)
        jumps = 0
        current_end = 0
        farthest = 0

        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = farthest

        return jumps
class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int jumps = 0, currentEnd = 0, farthest = 0;

        for (int i = 0; i < n - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }
}

Complexity Analysis

Time Complexity: O(n). We iterate through the array exactly once (from index 0 to n − 2). Each iteration does a constant amount of work — one max operation and one comparison.

Space Complexity: O(1). We only use three integer variables (jumps, currentEnd, farthest) regardless of the input size. No auxiliary data structures are needed.