Jump Game II | Leetcode 45 | Recursive and Greedy Solution

This problem asks: given an array nums where nums[i] is the maximum jump length from index i, find the minimum number of jumps needed to reach the last index. You start at index 0. You can always assume the last index is reachable as per the original LeetCode statement.

Here’s the [Problem Link] to begin with.

What does the problem say? (with examples)

You need to reach the last index in the fewest jumps.

Example 1

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Jump from index 0 -> 1 (length 1), then 1 -> 4 (length 3).

Example 2

Input: nums = [2,3,0,1,4]
Output: 2
Explanation: 0 -> 1, then 1 -> 4.

Key insight: you are minimizing the number of jumps, not the distance per jump. Large jumps can be good if they reduce the number of total moves.

Solution 1: Simple Recursion

Intuition and Approach

A straightforward idea is to try all possible jumps from the current index and choose the minimum among them. From index, you can jump up to nums[index] steps forward. Recursively compute the minimum jumps needed from each reachable next index and take the minimum.

This is a direct search of the decision tree:

• Base case: if index is at or beyond the last index, return the number of jumps taken so far.
• Otherwise, try every jump length from 1 to nums[index] and take the minimum of those results.

This approach is correct but explores many overlapping subproblems without caching, which makes it very slow on large inputs.

Code Implementation

class Solution:
    def solve(self, index, jump, lastIndex, nums):
        if index >= lastIndex:
            return jump
        minJump = float("inf")
        for i in range(1, nums[index] + 1):
            minJump = min(minJump, self.solve(index + i, jump + 1, lastIndex, nums))
        return minJump

    def jump(self, nums: List[int]) -> int:
        return self.solve(0, 0, len(nums) - 1, nums)

Code Explanation

• solve(index, jump, lastIndex, nums) returns the minimal jumps to reach or pass lastIndex starting from index, given that you have already taken jump jumps.
• If index >= lastIndex, you are done and return jump.
• Otherwise, you iterate possible next steps i from 1 to nums[index], recursively compute the answer for index + i, and track the minimum.
• jump(nums) starts the process from index 0 with 0 jumps.

Time and Space Complexity

• Precise: In the worst case, from each index you branch up to nums[index] times and recompute many subproblems repeatedly. This yields exponential time, commonly characterized as worse than O(2^n) for adversarial inputs.
• Simplified: Exponential time. Not feasible for large arrays.
• Space: The maximum recursion depth is at most n, so O(n) stack space.

Conclusion

Simple recursion is easy to understand but impractical without memoization or other optimizations. It suffers from massive recomputation and will time out on typical test cases.

Solution 2: Greedy (Optimal)

Intuition and Approach

A classic greedy strategy solves this in linear time by viewing the array as levels of reachable indices:

• Maintain the current window [left, right] of indices you can reach with the current number of jumps.
• Within this window, compute the farthest index you can reach with one more jump.
• Move to the next window and increment the jump count.
• Repeat until the right boundary reaches or passes the last index.

This is analogous to a breadth-first expansion across indices, but implemented with two pointers and a single pass.

Code Implementation

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        jumps = 0
        left = 0
        right = 0
        while right < n - 1:
            farthest = 0
            for i in range(left, right + 1):
                farthest = max(farthest, i + nums[i])
            left = right + 1
            right = farthest
            jumps += 1
        return jumps

Code Explanation

• left and right define the current range of indices reachable with jumps jumps.
• For every index i in the current range, compute how far you can go next as i + nums[i], and track the maximum as farthest.
• After scanning the range, set the next range to [right + 1, farthest] and increment jumps.
• The loop stops when right has reached or crossed the last index. The counter jumps is the minimal number of jumps.

This works because scanning all indices in the current reachable window ensures you consider every possible jump of length jumps + 1 and choose the furthest frontier for the next step, which minimizes the total number of jumps.

Time and Space Complexity

• Precise: Each index enters the inner loop exactly once across all iterations, so the total cost is O(n) for the scans plus O(n) for boundary updates, which is O(n + n).
• Simplified: O(n) time.
• Space: Only a few variables are used, so O(1) extra space.

Conclusion

The greedy window expansion is the optimal approach. It runs in linear time, uses constant space, and reliably computes the minimal number of jumps by expanding the furthest reachable frontier at each step.

Final Takeaway

• Simple recursion explores all choices and is correct but exponential in time.
• The greedy window method is optimal, achieving O(n) time and O(1) space by expanding the reachable range level by level and counting how many expansions are needed.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.