Jump Game

Jump Game is a clean greedy problem: at every index, keep track of the farthest position reachable so far. If the scan ever reaches an index beyond that boundary, the last index cannot be reached.

Problem

Given an array nums, each value represents the maximum jump length from that index. Return true if you can reach the last index, otherwise return false.

Example:

nums = [2,3,1,1,4]
result = true

From index 0, jump to index 1, then jump to the last index.

First Attempt

This solution already has the right idea: scan once, track the farthest reachable index, and stop early when the end is reachable.

public boolean canJump(int[] nums) {
    int farthestIndex = 0;
    int n = nums.length;

    for (int i = 0; i < n; i++) {
        if (i > farthestIndex) {
            return false;
        }

        farthestIndex = Math.max(farthestIndex, i + nums[i]);

        if (farthestIndex >= n - 1) {
            return true;
        }
    }

    return false;
}

Core Idea

The important invariant is:

Every index <= farthestIndex is reachable.

So when i > farthestIndex, the scan has reached a position that cannot be stepped on. No later jump can help, because jumps only start from reachable positions.

Clean Version

class Solution {
    public boolean canJump(int[] nums) {
        int farthestReach = 0;

        for (int i = 0; i < nums.length; i++) {
            if (i > farthestReach) {
                return false;
            }

            farthestReach = Math.max(farthestReach, i + nums[i]);

            if (farthestReach >= nums.length - 1) {
                return true;
            }
        }

        return true;
    }
}

The only small naming change is farthestReach, which makes the invariant easier to read.

Walkthrough

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

At index 1, farthestReach becomes 4, which reaches the last index. Return true.

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

Index 4 is greater than farthestReach, so return false.

Complexity

Takeaways

• Track the farthest reachable index, not every possible path.
• Return false as soon as the current index is unreachable.
• Greedy works because reachability only needs the best boundary so far.