Interview Classic 150 Questions P55 Jump Game

---

Timeline

Timeline

2025-10-02

init

Greedy, stack or queue, dynamic programming

---

Title:

P55 Jump Game

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

My first thought was to use queue traversal, BFS solution, using stack should also work, but you can see 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 an interesting solution that uses a greedy strategy. No need to think about the specific process, just jump as far as you can. If you jump past the last position, then you must be able to jump to 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, time complexity O(n^2)

• dp[i] = trueIndicates that i can be reached,
• dp[i] = falseIndicates that 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 continue searching
                }
            }
        }

        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;
        }
};