Reach the End by Jumping at Most Steps

medium array greedy

Problem

Each entry in the array is the maximum forward jump length from that index. Starting at index 0, decide whether the last index is reachable. The greedy idea: maintain a running farthest — the rightmost index reachable so far. As you walk left to right, if the current index already lies past farthest, you're stuck. Otherwise update farthest = max(farthest, i + nums[i]). Reaching or passing the last index means yes.

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

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