Back to solutions

Jump Game

MediumGreedy

Each value is the maximum jump length from that index. Return true if you can reach the last index.

Open problem
Constraints
  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 10^5

Greedy farthest reach

Time O(n)Space O(1)

Track the farthest index reachable so far. If the current index ever exceeds that reach, you are stuck; otherwise extend the reach. Success if the reach covers the last index.

#include <bits/stdc++.h>
using namespace std;

bool canJump(vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;
        reach = max(reach, i + nums[i]);
    }
    return true;
}