Jump Game II

Problem Description

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. Return the minimum number of jumps to reach nums[n - 1].

Key Insights

• You can jump from index i to any index up to i + nums[i].
• The goal is to minimize the number of jumps to reach the last index.
• A greedy approach works well here by always trying to jump to the farthest reachable index in each step.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be solved using a greedy algorithm. We will maintain the current end of the range that can be reached with the current number of jumps, and track the farthest point we can reach with the next jump. We iterate through the array, updating our jump count whenever we reach the end of the current jump range.

1. Initialize variables for the current end of range and the farthest point that can be reached.
2. Iterate through the array, updating the farthest point at each index.
3. When reaching the end of the current jump range, increment the jump count and update the current end to the farthest point.
4. Continue until reaching or exceeding the last index.

Code Solutions