Jump Game II

Updated on 04 June, 2025
Jump Game II header image

Problem Statement

You are presented with an integer array nums, where each element designates the maximal bound of a forward jump possible from its index position. Each position i in the array allows a jump to any index up to nums[i] steps ahead, provided it does not exceed the bounds of the array. Your goal is to determine the minimum number of jumps needed to traverse from the starting point nums[0] to the last element nums[n - 1], with the assurance that reaching the final element is always possible given any starting configuration of the array.

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

Constraints

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

Approach and Intuition

The task at hand is to navigate an array using the values as potential jump lengths to reach the last index with the fewest jumps possible. Here's how to understand and solve this problem:

  1. Start from the first index of the array. This position indicates the furthest jump you can make initially, but making the maximum available jump is not always the optimal first move.

  2. Keep track of the maximum range you can reach with the current number of jumps. This involves monitoring the furthest point that can be reached with the next jump, as each index might allow jumping further than the current maximum range.

  3. As you move through the array within the reachable range, update the furthest distance you could reach. Once you exceed the current maximum range with your index, increment the jump counter, indicating a jump has been made to extend the range.

  4. Keep iterating until you've either reached or surpassed the last index. Each time the current index equals the maximum range reachable with the current jumps, increment your jump counter, move your range extent to what was previously calculated as the furthest reachable, and continue.

  5. Your loop or iteration can end once the last index is included in the current maximum range, ensuring the fewest jumps have been determined.

By following this greedy strategy—always trying to extend to the furthest reachable point in the next jump—optimality in terms of minimal jumps is achieved. The efficiency of this approach lies in not just jumping to the furthest point immediately, but considering how far the subsequent jumps from each accessible index can take you, thereby minimizing the total jumps required.

Solutions

  • C++
  • Java
  • C
  • JavaScript
  • Python
cpp
class Solution {
public:
    int countMinimumJumps(vector<int>& jumps) {
        int jumpsNeeded = 0, length = int(jumps.size());
        int currentEnd = 0, farthest = 0;

        for (int position = 0; position < length - 1; ++position) {
            farthest = max(farthest, position + jumps[position]);

            if (position == currentEnd) {
                jumpsNeeded++;
                currentEnd = farthest;
            }
        }

        return jumpsNeeded;
    }
};

The given problem is a classical dynamic programming challenge, often involving an array in which each element represents the maximum jump length at that position, and the goal is to determine the minimum number of jumps needed to reach the last index of the array.

  • The solution uses a greedy algorithm approach to find the minimum number of jumps required:
  1. Initialize variables jumpsNeeded to count the total number of jumps, currentEnd to mark the furthest point that can be reached with the current number of jumps, and farthest to keep track of the farthest point that can be reached from the current point.
  2. Iterate through the array, and for each element, update farthest to capture the maximum range that can be jumped to from the current index.
  3. If you reach the end of the range covered by currentEnd, increment jumpsNeeded and update currentEnd to farthest to expand the range for the next set of jumps.
  4. Continue this process until you reach or surpass the last index of the array.

This greedy algorithm effectively ensures you're making the largest possible jump at each step, minimizing the total number of jumps needed to reach the end of the array. The use of max ensures that at each step, the decision considers the best possible progression given the current and past positions, ensuring efficiency and correctness of the algorithm.

java
class Solution {
    public int jumpToReachEnd(int[] sequence) {
        int jumpsCount = 0, length = sequence.length;
        int endPosition = 0, furthest = 0;

        for (int pos = 0; pos < length - 1; ++pos) {
            furthest = Math.max(furthest, pos + sequence[pos]);

            if (pos == endPosition) {
                jumpsCount++;
                endPosition = furthest;
            }
        }

        return jumpsCount;
    }
}

The Jump Game II problem requires calculating the minimum number of jumps to reach the end of an array where each integer indicates the maximum number of indices one can jump forward from that index. Here's a concise overview of the approach followed in the Java solution:

  • Initially, set jumpsCount to zero. This variable records the number of jumps required.
  • Use endPosition to track the farthest position that can be reached with the current number of jumps.
  • Use furthest to record the maximum reach from any position within the current range set by endPosition.

The solution employs a loop to iterate over the array:

  • Update furthest to hold the maximum of itself and the sum of current position and its value. This computes the farthest position reachable up to this point.
  • Check if the current position matches the endPosition. If true, it signifies the need to make a new jump because one cannot go further without increasing the jump count.
    • Increment jumpsCount.
    • Update endPosition to furthest to expand the range that can be reached with the new count of jumps.
  • The loop stops just before the last element because reaching the last element means the goal is achieved, and no further jumps are necessary from there.

The solution executes in O(n) time complexity as it involves a single scan through the array. This efficient approach ensures minimal computational overhead for large arrays. The method returns jumpsCount as the minimum number of jumps needed to reach the end of the array.

c
int calculateJumps(int* arr, int len) {
    int jumpsCount = 0;
    int currentEnd = 0, furthest = 0;
    for (int index = 0; index < len - 1; ++index) {
        furthest = (furthest > index + arr[index]) ? furthest : index + arr[index];
        if (index == currentEnd) {
            jumpsCount++;
            currentEnd = furthest;
        }
    }
    return jumpsCount;
}

The provided C program is designed to solve the minimum number of jumps required to reach the end of an array where each element represents the maximum jump length at that position. The function calculateJumps takes an array of integers and its length as input and returns the minimum number of jumps needed.

  • The function initializes three variables: jumpsCount to track the number of jumps, currentEnd to mark the boundary of the current jump range, and furthest to store the furthest position reachable within the current jump range.
  • It iterates through the array using a for loop, excluding the last element (as reaching the last element concludes the problem).
  • During each iteration, the function updates the furthest variable with the maximum range possible from the current position and updates the currentEnd when the end of the range for the current jump is reached. Whenever the currentEnd is updated, the jumpsCount is incremented as it signifies making a new jump.
  • The loop structure ensures that the function calculates the minimal jumps required by always extending the jump to the furthest reachable point before committing to the next jump.
  • Finally, the function returns the total number of jumps calculated.

This method efficiently determines the minimum jumps using a greedy algorithm approach, ensuring that every jump extends to the maximum possible length, thus minimizing the total number of jumps needed.

js
var countJumps = function (values) {
    let jumps = 0,
        length = values.length;
    let end = 0,
        furthest = 0;
    for (let index = 0; index < length - 1; ++index) {
        furthest = Math.max(furthest, index + values[index]);
        if (index === end) {
            ++jumps;
            end = furthest;
        }
    }
    return jumps;
};

The provided JavaScript function countJumps calculates the minimum number of jumps required to reach the end of an array where each element represents the maximum jump length from that position. Follow this summary to understand the solution:

  • Initialize two integers, jumps and end, to zero and furthest to zero. These will track the number of jumps made, the current end of the jump, and the furthest point that can be reached, respectively.

  • Loop through each element in the array except the last one using a for loop:

    • Update furthest to be the maximum of furthest or the sum of the current index and the value at that index in the array. This keeps track of the farthest point reachable from the current index or from any of the previous indices within the current jump.
    • Check if the current index is equal to end (initially set to zero but updates within the loop). This condition is true when you've reached the end of what your current jump can reach:
      1. Increment the jumps variable as you need another jump to continue.
      2. Update end to furthest, indicating that the new boundary to reach in the next jump is the furthest point found in the current iteration.
  • Return the jumps variable after exiting the loop, which now contains the minimum number of jumps needed to reach the end of the array.

By following these steps, the function effectively calculates and returns the minimal jumps needed, leveraging a greedy algorithm approach to always jump as far as possible within the current reach before incrementing the jump count. This ensures optimal performance and the least number of jumps are made.

python
class Solution:
    def calculateJumps(self, jumps: List[int]) -> int:
        jumps_count, length = 0, len(jumps)
        current_end, furthest = 0, 0

        for index in range(length - 1):
            furthest = max(furthest, index + jumps[index])
            if index == current_end:
                jumps_count += 1
                current_end = furthest

        return jumps_count

The calculateJumps function in Python is designed to solve the problem of finding the minimum number of jumps required to reach the end of a list. Each element in the list represents the maximum jump length from that position. Here is the logical breakdown:

  • Initialize jumps_count to track the number of jumps, current_end to mark the end of the range achievable with the current number of jumps, and furthest to store the farthest point that can be reached.

  • Iterate through the list up to the second last element. For each position, update furthest to be the maximum of the current furthest and the index plus the jump value at that index.

  • If the current index matches current_end, it indicates the need for a new jump. Hence, increment the jumps_count and update current_end to furthest.

  • Continue until the loop finishes, then return the total jumps_count. This count shows the minimum jumps needed to reach or surpass the final index.

This method operates efficiently by dynamically tracking the range reachable for each jump, ensuring an optimal solution with each iteration.

Comments

No comments yet.