Classic 150 Interview Questions P45 Jump Game II

---

Timeline

Timeline

2025-10-02

init

Greedy, Dynamic Programming

---

Problem:

P45 Jump GameII

https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

My first thought was dynamic programming.
Let dp[i] denote the minimum number of jumps to reach i, with -1 meaning unreachable. Then for 0 <= j < i, if j can reach i, i.e., nums[j] + j >= i and dp[j] != -1

$$dp[i] = min (dp[j] +1)$$

If there is no reachable j, then

$$dp[i] = -1$$

#include <climits>
#include <vector>
using std::vector;

class Solution {
public:
  int jump(vector<int> &nums) {
    // dp[i] represents the minimum number of jumps to reach i, -1 means unreachable
    // For 0 <= j < i
    // if(nums[j] + j >= i ) dp[i] = dp[j] + 1;
    // If no such j exists, dp[i] = -1;
    int n;
    int min;
    n = nums.size();
    vector<int> dp(n, -1);

    dp[0] = 0;
    for (int i = 1; i < n; i++) {
      min = INT_MAX;
      for (int j = 0; j < i; j++) {
        if (nums[j] + j >= i && dp[j] != -1 && dp[j] + 1 < min) {
          min = dp[j] + 1;
        }
      }
      if (min != INT_MAX) {
        dp[i] = min;
      } else {
        dp[i] = -1;
      }
    }
    return dp[n - 1];
  }
};

This problem is actually a classic greedy problem. Looking from the back to the front, the last position must have been jumped to from some previous position, but there may be multiple such previous positions. In that case, we greedily choose the farthest one (because either way it takes one more step, choosing the one closer to the start will definitely reduce the number of jumps. This is because if two positions can both reach the last position, with a being earlier and b being later, we would definitely choose a, since the steps to reach a are necessarily less than or equal to the steps to reach b). After choosing, this selected position becomes the new last position.

class Solution {
public:
    int jump(vector<int>& nums) {
        int position = nums.size() - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
};

It can also be adapted using the idea of the following problem.

P55 Jump Game

https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150

Official solution:

If we perform a forward search in a greedy manner, each time finding the farthest reachable position, we can obtain the minimum number of jumps in linear time.

For example, for the array [2,3,1,2,4,2,3], the initial position is index 0. Starting from index 0, the farthest reachable index is 2. Among the positions reachable from index 0, the value at index 1 is 3, and starting from index 1 can reach a farther position, so the first step goes to index 1.

Starting from index 1, the farthest reachable index is 4. Among the positions reachable from index 1, the value at index 4 is 4, and starting from index 4 can reach a farther position, so the second step goes to index 4.

fig1

In the specific implementation, we maintain the maximum index position currently reachable, denoted as the boundary. We traverse the array from left to right. When we reach the boundary, we update the boundary and increase the jump count by 1.

When traversing the array, we do not visit the last element, because before visiting the last element, our boundary must be greater than or equal to the last position; otherwise, we would not be able to jump to the last position. If we visit the last element, in the case where the boundary is exactly the last position, we would add an ‘unnecessary jump count’, so we do not need to visit the last element.

class Solution {
public:
    int jump(vector<int>& nums) {

        int i = 0, j = 0, n = nums.size();

        int max_pos = 0;
        int last_end = 0;
        int step = -1;

        for(i = 0; i< n;i++){
            max_pos = std::max(max_pos, i + nums[i]);
            if(i == last_end){
                last_end = max_pos > n-1 ? n-1: max_pos;
                step++;
            }
        }
        return step;

    }
};

leetcode hot 100 rewrite

#include <vector>
using std::vector;

class Solution {
    public:
        int jump(vector<int> &nums)
        {
                // Jump from back to front, greedily choosing the farthest one that can jump to the current position.
                int i, n = nums.size();
                int curr = n - 1;
                int cnt = 0;

                while (curr > 0) {
                        for (i = 0; i < curr; i++) {
                                if (nums[i] + i >= curr){
                                        curr = i;
                                        cnt++;
                                        break;
                                }

                        }
                }

                return cnt;
        }
};