45. Jump Game II - Leetcode Solution

LeetCode problem Solution code

💡 Step-by-Step Thought Process

Brute Force

The problem requires finding the minimum number of jumps needed to reach the last index of an array, where each element nums[i] indicates the maximum jump length from index i.

The brute-force solution uses a recursive backtracking approach to explore all possible jump sequences. Here’s how it works:

  • Initialization: We use a list smallest to store the minimum number of jumps found, initialized to infinity.
  • Backtracking Function: The backtrack(i, jumps) function takes the current index i and the number of jumps taken:
    • If i equals n-1 (the last index), update smallest[0] with the minimum of its current value and jumps.
    • Otherwise, compute the maximum jump distance max_jump = nums[i] and the farthest reachable index max_reachable_index = min(i + max_jump, n-1).
    • For each possible next index new_index from max_reachable_index down to i+1, recursively call backtrack(new_index, jumps+1).
  • Execution and Result: Call backtrack() starting from index 0 with 0 jumps, and return smallest[0].
  • Why This Works: The backtracking explores every possible sequence of jumps, ensuring that the minimum number of jumps to reach the last index is found. By updating smallest only when the last index is reached, we track the best solution across all paths.
  • Time and Space Complexity: The solution explores up to nums[i] choices at each index, leading to an exponential time complexity of O(k^n) in the worst case, where k is the maximum jump length and n is the array length. The space complexity is O(n) due to the recursion stack.

Code Solution (Brute Force)

# Brute Force
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        smallest = [float('inf')]

        def backtrack(i=0, jumps=0):
            if i == n-1:
                smallest[0] = min(smallest[0], jumps)
                return
            
            max_jump = nums[i]
            max_reachable_index = min(i+max_jump, n-1)

            for new_index in range(max_reachable_index, i, -1):
                backtrack(new_index, jumps+1)
        
        backtrack()
        return smallest[0]

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int jump(std::vector<int>& nums) {
        int n = nums.size();
        int smallest = INT_MAX;

        backtrack(0, 0, nums, n, smallest);
        return smallest;
    }

private:
    void backtrack(int i, int jumps, std::vector<int>& nums, int n, int& smallest) {
        if (i == n - 1) {
            smallest = std::min(smallest, jumps);
            return;
        }

        int maxJump = nums[i];
        int maxReachableIndex = std::min(i + maxJump, n - 1);

        for (int newIndex = maxReachableIndex; newIndex > i; newIndex--) {
            backtrack(newIndex, jumps + 1, nums, n, smallest);
        }
    }
};

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] smallest = {Integer.MAX_VALUE};

        backtrack(0, 0, nums, n, smallest);
        return smallest[0];
    }

    private void backtrack(int i, int jumps, int[] nums, int n, int[] smallest) {
        if (i == n - 1) {
            smallest[0] = Math.min(smallest[0], jumps);
            return;
        }

        int maxJump = nums[i];
        int maxReachableIndex = Math.min(i + maxJump, n - 1);

        for (int newIndex = maxReachableIndex; newIndex > i; newIndex--) {
            backtrack(newIndex, jumps + 1, nums, n, smallest);
        }
    }
}

var jump = function(nums) {
    var n = nums.length;
    var smallest = [Infinity];

    function backtrack(i, jumps) {
        if (i === n - 1) {
            smallest[0] = Math.min(smallest[0], jumps);
            return;
        }

        var maxJump = nums[i];
        var maxReachableIndex = Math.min(i + maxJump, n - 1);

        for (var newIndex = maxReachableIndex; newIndex > i; newIndex--) {
            backtrack(newIndex, jumps + 1);
        }
    }

    backtrack(0, 0);
    return smallest[0];
};

Inefficiency in Brute-Force

The brute-force solution is highly inefficient because it explores all possible jump combinations recursively, leading to an exponential time complexity of O(k^n). For each index, it tries up to nums[i] possible next indices, and this branching repeats for each subsequent index, resulting in a combinatorial explosion for large arrays or large jump values.

Additionally, the solution recomputes paths that may overlap, redundantly exploring the same indices multiple times, which wastes computational effort. This makes it impractical for large inputs.

Fix with Optimal Solution

The optimal solution uses a greedy approach to achieve O(n) time complexity. Instead of exploring all possible jumps, it maintains two pointers: end (the farthest index reachable with the current number of jumps) and far (the farthest index reachable with one more jump). Here’s how it improves:

  • Greedy Traversal: Iterate through the array, updating far as the maximum reachable index from the current position (i + nums[i]). When the current index i reaches end, increment the jump count and update end to far, effectively choosing the farthest reachable point as the next jump’s boundary.
  • Efficiency: This processes each index exactly once, resulting in O(n) time complexity. It avoids redundant exploration by making a single pass and greedily selecting the optimal jump point at each step.
  • Space: Only a few variables are used, maintaining O(1) space complexity.
  • Why It’s Better: The greedy approach leverages the fact that to minimize jumps, we should always jump as far as possible within the current jump’s reach, reducing the problem to a linear scan. This eliminates the exponential branching of the brute-force method, making it scalable for large inputs.

Code Solution (Optimal)

# Optimal    
class Solution:
    def jump(self, nums: List[int]) -> int:
        smallest = 0
        n = len(nums)
        end, far = 0, 0

        for i in range(n-1):
            far = max(far, i+nums[i])
            
            if i == end:
                smallest += 1
                end = far
        
        return smallest
        # Time: O(n)
        # Space: O(1)
        
#include <vector>
#include <algorithm>

class Solution {
public:
    int jump(std::vector<int>& nums) {
        int smallest = 0;
        int n = nums.size();
        int end = 0;
        int far = 0;

        for (int i = 0; i < n - 1; i++) {
            far = std::max(far, i + nums[i]);
            
            if (i == end) {
                smallest++;
                end = far;
            }
        }

        return smallest;
    }
};

class Solution {
    public int jump(int[] nums) {
        int smallest = 0;
        int n = nums.length;
        int end = 0;
        int far = 0;

        for (int i = 0; i < n - 1; i++) {
            far = Math.max(far, i + nums[i]);
            
            if (i == end) {
                smallest++;
                end = far;
            }
        }

        return smallest;
    }
}

var jump = function(nums) {
    var smallest = 0;
    var n = nums.length;
    var end = 0;
    var far = 0;

    for (var i = 0; i < n - 1; i++) {
        far = Math.max(far, i + nums[i]);
        
        if (i == end) {
            smallest++;
            end = far;
        }
    }

    return smallest;
};

Detailed Explanation

Understanding the Problem

"Jump Game II" asks for the minimum number of jumps required to reach the last index of an array. Each element nums[i] in the array represents the maximum number of steps you can jump forward from that index. The goal is to reach the end of the array using the fewest jumps possible.

Key Insight and Strategy

To solve this efficiently, we apply a greedy algorithm that tracks the farthest reachable index at every step. The idea is to progress level by level, similar to Breadth-First Search (BFS) in a graph, where each level represents a jump. Instead of examining all jump paths (which leads to exponential time), we compute the farthest index reachable with the current number of jumps, then increase the jump count only when we must extend our reach.

Step-by-Step Algorithm

  1. Initialize three variables: jumps to count the number of jumps, end to mark the range of the current jump, and far to track the farthest index reachable in the next jump.
  2. Iterate through the array from index 0 to n - 2 (we stop before the last index since we aim to reach it).
  3. At each step i, calculate far = max(far, i + nums[i]) to find the furthest index we can jump to from the current segment.
  4. If i equals end, we’ve reached the boundary of the current jump level, so we increment jumps and update end = far.

Example

Consider nums = [2, 3, 1, 1, 4]. Initially, far = 0 and end = 0. On the first jump, you can go up to index 2. On the second jump, from indices 1 or 2, you can reach the end (index 4). So, the answer is 2 jumps.

Why the Greedy Approach Works

The greedy strategy works because we always choose the jump that allows us to reach the farthest possible point. This mimics a level-order traversal in BFS and guarantees the fewest jumps needed. We don’t need to explore all paths, only the farthest reachable range from each position.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array. Each index is visited once.

Space Complexity: O(1), since we use only a constant number of variables.

Conclusion

"Jump Game II" is a classic greedy problem that demonstrates how to minimize steps when faced with overlapping choices. By focusing on the farthest reachable index within each jump range, we avoid unnecessary computations and achieve optimal performance. This problem reinforces a powerful lesson in greedy design: local optimal decisions can lead to globally optimal results when applied strategically.

NEW!Need help landing software roles? 💡