Problem Statement

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

LeetCode:

• https://leetcode.com/problems/jump-game-ii/description/

Constraints

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
It's guaranteed that you can reach nums[n - 1].

Examples

Example 1:

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

Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

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

Different Approaches

1️⃣ Brute Force (Recursion) (TLE)

Since we are given different choices at each index (i.e., we can jump from 1 to nums[i] steps), and we want to explore all possible paths to find the minimum number of jumps, recursion is a natural fit.
Recursion is especially useful when choices or decisions need to be explored one by one, like in this case.

Approach:

1. Base Case:
   1. If you're at or beyond the last index (i >= n - 1), you’ve reached the goal, so return 0 jumps needed.
2. Recursive Case:
   1. Try every possible jump length from 1 to nums[i], and:
   2. Recursively solve for the next position (i + step)
   3. Add 1 jump for the current move
   4. Take the minimum among all options
3. Return the minimum jumps from the current index to the end.

Code:

class Solution {
public:
    int solve(vector<int>& nums, int i) {
        // Base case: reached or passed last index
        if (i >= nums.size() - 1) {
            return 0;
        }

        int mini = 1e9; // large number
        for (int step = 1; step <= nums[i]; step++) {
            int jumps = 1 + solve(nums, i + step); // take the jump
            mini = min(mini, jumps);               // track the minimum
        }
        return mini;
    }

    int jump(vector<int>& nums) {
        return solve(nums, 0); // start from index 0
    }
};

Complexity Analysis:

• Time Complexity:O(n^n)

  • In the worst case because from each index you may try all nums[i] paths, leading to an explosion of recursive calls.

    For example:
    If nums = [3, 3, 3, 3, 3], then:
    
    From index 0 → try jumps to index 1, 2, 3
    
    From index 1 → again try jumps to next 3 indices, and so on.
    So, it’s a tree with branching factor ~3, depth n, hence exponential.

• Space Complexity:O(n)
  • For the recursion stack in the worst case (when you jump just 1 step each time).

2️⃣ Memoization

If we notice we have the overlapping subproblems in the recursive approach. So we can memoize it.

Code:

class Solution {
public:
    int solve(vector<int>& nums, int i, vector<int>& dp) {
        if (i >= nums.size() - 1) {
            return 0;
        }

        if (dp[i] != -1) return dp[i]; // return cached result

        int mini = 1e9;
        for (int step = 1; step <= nums[i]; step++) {
            int next = i + step;
            if (next < nums.size()) {
                int jumps = 1 + solve(nums, next, dp);
                mini = min(mini, jumps);
            }
        }

        return dp[i] = mini; // store and return
    }

    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, -1);
        return solve(nums, 0, dp);
    }
};

Complexity Analysis:

• Time Complexity:O(n^2)
  • For each index i, we compute the result once.
  • For each i, we may explore up to nums[i] steps – worst case up to n → total ~ O(n^2)
• Space Complexity:O(n)
  • For the dp array and recursion stack.

3️⃣ Greedy Approach (Optimal)

Intuition:

• You’re at position i, and nums[i] tells you how far you can jump forward.
• The goal is to reach the last index using the minimum number of jumps.
• Instead of trying all paths (like recursion/DP), we scan the array in one pass and keep track of:
  • How far we can go in the current jump range.
  • When we exhaust that range, we jump and start a new range.
• It’s like layered BFS — at each level, you jump to the farthest node in that layer.

Approach:

1. Start from index 0.
2. Keep extending the farthest index you can reach in the current level.
3. When you reach the end of the current jump (curEnd), you must jump and move to the next level (update curEnd = farthest).
4. Repeat until you reach or pass the last index.

Code:

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0;        // Total number of jumps made
        int curEnd = 0;       // End of the current jump range
        int farthest = 0;     // Farthest index reachable so far

        // We go only till the second last index
        // because once we reach the last index, we don't need to jump anymore
        for (int i = 0; i < nums.size() - 1; i++) {
            // Update the farthest reachable index from this point
            farthest = max(farthest, i + nums[i]);

            // If we've reached the end of the current range,
            // we need to make a jump and update the current range
            if (i == curEnd) {
                jumps++;            // Take the jump
                curEnd = farthest;  // Update the current range
            }
        }

        return jumps;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • We loop through the array once, updating variables – no nested loops or recursion.
• Space Complexity:O(1)
  • We use only constant extra space: jums, currEnd, farthest.