Jump Game

Problem Overview

Given an array where each element represents your maximum jump length from that position, determine whether you can reach the last index starting from the first.

Why solve this?

The first genuinely greedy array problem in this course — instead of simulating every possible sequence of jumps, it's solved by tracking a single running value: the farthest index reachable so far.

Pattern Recognition

Whenever a problem asks whether some goal is reachable through a sequence of choices, and each choice's effect is a simple numeric bound like a jump length, check whether tracking the single best reachable bound so far — rather than exploring every path — is enough.

Prerequisites

• Basic array traversal and running-maximum tracking (see Second Largest Element in an Array).

Hints

1. You don't need to try every possible sequence of jumps — track one number: the farthest index reachable so far.
2. Walk the array left to right. At each index you can actually reach, update farthest = max(farthest, index + nums[index]).
3. If you ever reach an index beyond the current farthest before updating it, you're stuck — and if farthest ever reaches or passes the last index, you've already won.

Approach

Track one running value, farthest, the largest index reachable using jumps from any position visited so far. Scan the array left to right: at each index i, if i is already beyond farthest, that index (and everything after it) is unreachable, so the answer is false. Otherwise, update farthest to max(farthest, i + nums[i]). If farthest ever reaches or exceeds the last index, the array is fully reachable and the answer is true. This greedy update is always safe because reaching a farther index can never hurt — every position reachable from a closer index is also reachable from (or before) a farther one.

Code

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

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy