Jump Game II

Practice here

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

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

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

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

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

Recursive Approach#

• Intuition: From every index, try all possible jumps and recurse; the minimum jump count across all paths that reach the last index is the answer. This exhaustively explores every reachable sequence of positions.
• Mechanics: Starting at index 0 with 0 jumps, the helper tries every step size from 1 to nums[idx], incrementing the jump counter on each recursive call. When the last index is reached, the running count is compared against a global minimum.
• Trade-off: Exponential time O(2^n) due to overlapping subproblems — each index may be reached many times via different paths. Guaranteed TLE on large inputs. DP memoization or the greedy approach is required.

class Solution {
public:
    int minJumps;
    void jumpsUtil(vector<int>& nums, int idx, int jumps)
    {
        if(idx>=nums.size())
            return;

        if(idx==nums.size()-1)
            minJumps = min(minJumps, jumps);

        for(int i=1;i<=nums[idx];i++){
            jumpsUtil(nums, idx+i, jumps+1);
        }
    }
    int jump(vector<int>& nums) {
        minJumps = INT_MAX;
        jumpsUtil(nums, 0, 0);
        return minJumps;
    }
};

Time Complexity: O(2ⁿ) -> TLE

Space Complexity: O(n)

DP Approach#

• Intuition: Define jumps[i] as the minimum number of jumps to reach index i. For every index i, look back at all indices j < i that can reach i (i.e., j + nums[j] >= i) and set jumps[i] = min(jumps[i], jumps[j] + 1). This avoids recomputing overlapping subproblems.
• Mechanics: Initialise jumps[0] = 0 and all others to INT_MAX. A nested loop iterates i from 1 to n-1 and j from 0 to i-1, updating jumps[i] whenever j can reach i. The answer is jumps[n-1].
• Trade-off: O(n²) time — a major improvement over the exponential recursive approach but still suboptimal. The greedy approach eliminates the inner loop entirely, achieving O(n) time and O(1) space.

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

        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[j]+j>=i)
                    jumps[i] = min(jumps[i], jumps[j]+1);
            }
        }
        return jumps[n-1];
    }
};

Time Complexity: O(n²)

Space Complexity: O(n)

Greedy Approach#

Intuition: Think of each jump as a "wave" — the first wave covers all indices reachable in 1 jump, the second wave covers all indices reachable from those, and so on. The number of waves needed to reach the last index is the minimum jump count. You don't need to actually pick which index to jump to within a wave; just track how far the current wave can extend.

• You track the farthest index you can reach so far (coverage).
• You also keep track of the end of your current jump range (lastIdx).
• As you walk through the array:
  • Update coverage with the farthest point reachable from any index within the current range.
  • When you reach lastIdx, it means you’ve finished the current jump — so you increment jumps and set lastIdx = coverage to start a new jump range.
• If at any point coverage reaches or exceeds the last index, you can stop.

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        if(n==1)
            return 0;

        int coverage = 0, lastIdx=0, jumps=0;

        for(int i=0;i<n;i++)
        {
            coverage = max(coverage, i+nums[i]);

            if(i==lastIdx){
                lastIdx = coverage;
                jumps++;

                if(coverage >= n-1)
                    break;
            }
        }
        return jumps;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)