Jump Game

medium array greedy

Problem

Given an array of non-negative integers nums, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index.

Inputnums = [2, 3, 1, 1, 4]

Outputtrue

From 0 you can reach index 1 (jump 1) or 2 (jump 2). From 1 you can reach up to 1+3 = 4 — the end.

nums (non-negative, comma-separated)

def can_jump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True

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

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

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

Explanation

The question is just yes/no: can you reach the last index? Instead of exploring all jump combinations, we greedily track a single number — farthest, the furthest index we know is reachable so far.

We scan left to right. At each index i, the first thing we check is whether i itself is even reachable: if i > farthest, there is a gap we can never cross, so we immediately return False.

Otherwise, standing at i we could jump up to i + nums[i], so we update farthest = max(farthest, i + nums[i]). This keeps farthest as the best reach considering every position we've been able to stand on.

If the loop finishes without ever finding an unreachable index, the end is reachable and we return True.

Example: nums = [2, 3, 1, 1, 4]. Start with farthest = 0. At i=0, reach becomes 2; at i=1, reach jumps to 1 + 3 = 4, which already covers the last index. No index is ever beyond farthest, so the answer is true.

Time: O(n) Space: O(1)