Top 150 Interview Questions P55 Jump Game

---

Timeline

Timeline

2025-10-02

init

Greedy, stack or queue, dynamic programming

---

Problem:

P55 Jump Game

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

The first thing I thought of was using a queue to traverse, a BFS solution. Using a stack should also work, but you can see that this complexity is quite large.

#include <queue>
#include <unordered_set>
#include <vector>

using std::queue;
using std::unordered_set;
using std::vector;

class Solution {
    public:
        bool canJump(vector<int> &nums)
        {
                int n = nums.size();
                int jmp;
                int curr;
                int i, tmp;
                queue<int> que;
                unordered_set<int> uset;
                if (n == 1) {
                        return true;
                }

                que.push(0);
                uset.insert(0);
                do {
                        curr = que.front();
                        jmp = nums[curr];
                        if (jmp == 0) {
                                que.pop();
                                uset.erase(curr);
                                continue;
                        }

                        for (i = 1; i <= jmp; i++) {
                                tmp = curr + i;
                                if (tmp == n - 1) {
                                        return true;
                                } else if (tmp < n && uset.count(tmp) == 0) {
                                        que.push(tmp);
                                        uset.insert(tmp);
                                }
                        }
                        uset.erase(curr);
                        que.pop();

                } while (!que.empty());

                return false;
        }
};

#include <stdio.h>
int main()
{
        Solution S;
        vector<int> vec = { 2, 5, 0, 0 };
        printf("%d\n", S.canJump(vec));
}

After reading the comments, there is a very interesting solution that uses a greedy strategy. You don’t need to think about the specific process; just jump as far as you can. If you can jump past the last position, then you will definitely be able to reach the last position.

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i, n = nums.size();
        int max_reach_pos = 0;

        for( i = 0; i < n && i <= max_reach_pos; i++ ){
            max_reach_pos = std::max(max_reach_pos, i + nums[i]);
        }

        return (max_reach_pos >= n-1);

    }
};

This problem can also be solved with dynamic programming, with a time complexity of O(n^2).

• dp[i] = trueIndicates that position i can be reached,
• dp[i] = falseIndicates that position i cannot be reached

Then for position i, if there exists j (0 <= j < i) that can be reached, and the maximum jump distance from j can cover i, that is:

if(j+nums[j]>=i){
  dp[j] = true;
}else{
  dp[j] = false;
}

#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> dp(n, false);
        dp[0] = true;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;  // As long as it can be reached, there is no need to keep looking.
                }
            }
        }

        return dp[n-1];
    }
};

LeetCode Hot 100 rewrite, greedy strategy

#include <vector>
using std::vector;

class Solution {
    public:
        bool canJump(vector<int> &nums)
        {
                int i, n = nums.size();
                int max_reach = 0;

                for (i = 0; i < n && i <= max_reach; i++) {
                        max_reach = std::max(max_reach, i + nums[i]);
                        if (max_reach >= n - 1)
                                return true;
                }

                return false;
        }
};