83. Jump Game · DSA Practice

You start at index 0; nums[i] is the maximum jump length from position i. Can you reach the last index?

Example 1

Input: nums = [2,3,1,1,4]

Output: true

Example 2

Input: nums = [3,2,1,0,4]

Output: false

Hint 1

Track the furthest index you can reach. If you ever stand beyond it, you are stuck.

Greedy

Approach 1: DP from the end

good[i] if some jump lands on a good index.

⏱ Time O(n²)💾 Space O(n)

Approach 2: Greedy reach ✅

One pass with the furthest reachable index.

⏱ Time O(n)💾 Space O(1)

Reference solution for Greedy reach (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reach = 0                          # furthest index reachable so far
        for i, x in enumerate(nums):
            if i > reach:
                return False               # stuck before index i
            reach = max(reach, i + x)
        return True

class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;                     // furthest reachable index
        for (int i = 0; i < nums.length; i++) {
            if (i > reach) return false;
            reach = Math.max(reach, i + nums[i]);
        }
        return true;
    }
}

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int reach = 0;                     // furthest reachable index
        for (int i = 0; i < (int)nums.size(); i++) {
            if (i > reach) return false;
            reach = max(reach, i + nums[i]);
        }
        return true;
    }
};

function canJump(nums) {
  let reach = 0; // furthest reachable index
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Greedy & Intervals.