Jump Game — Greedy Max Reach O(n) [Meta, Amazon]

Problem Statement

Each element in nums represents your max jump length at that position. Can you reach the last index?

Input: [2,3,1,1,4] → true Input: [3,2,1,0,4] → false

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(1) space

Intuition

Track maxReach = furthest index reachable so far. If current index i > maxReach, we can't reach i → return false. Otherwise update maxReach = max(maxReach, i + nums[i]).

C++ Solution

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

Java Solution

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

Python Solution

def canJump(nums):
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach: return False
        max_reach = max(max_reach, i + jump)
    return True

JavaScript Solution

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

Complexity: O(n) time, O(1) space

Jump Game II (min jumps): Greedy BFS — track current range and next range, increment jumps when range exhausted.