Jump Game LeetCode: Greedy One-Pass Solution Explained

Jump Game (#55) is one of the cleanest greedy problems on LeetCode. You are given an array of non-negative integers where each element represents the maximum jump length from that position. Your goal is simple: determine whether you can reach the last index starting from the first.

What makes this problem special is that the optimal solution requires exactly one variable and one pass through the array. No dynamic programming tables, no BFS queues, no recursion — just a single integer tracking the farthest index you can reach.

This problem is a gateway to the greedy reachability pattern, which extends directly to Jump Game II (#45) and other interval-coverage problems. Understanding it deeply will make several related problems trivial.

Given an integer array nums, you start at index 0. Each element nums[i] tells you the maximum number of positions you can jump forward from index i. You need to determine if you can reach the last index nums.length - 1.

For example, in [2,3,1,1,4], starting at index 0 you can jump up to 2 positions. From index 1 you can jump up to 3 positions. The question is not about finding a specific path — it is about whether any valid sequence of jumps gets you to the end.

The key insight is that you do not need to track every possible path. You only need to know the farthest position reachable at each step. If the farthest reachable position ever falls behind your current index, you are stuck.

The greedy solution uses a single variable called maxReach that tracks the farthest index you can possibly reach. You iterate through the array from left to right, and at each index i you check two things.

First, if i is greater than maxReach, you cannot reach this index at all — return false immediately. Second, update maxReach to be the maximum of its current value and i + nums[i], which is the farthest you could reach by jumping from index i.

If you make it through the entire loop without getting stuck, maxReach must be at or beyond the last index, so return true. The time complexity is O(n) with a single pass, and space complexity is O(1) since you only use one extra variable.

The implementation is remarkably compact. Initialize maxReach to 0. Loop through each index i from 0 to nums.length - 1. If i exceeds maxReach, return false. Otherwise set maxReach to Math.max(maxReach, i + nums[i]). After the loop, return true.

You can also add an early exit: if maxReach is already greater than or equal to the last index at any point during the loop, return true immediately. This optimization does not change the worst-case complexity but can speed up average cases.

Some developers prefer to iterate only while i is less than or equal to maxReach, which naturally handles the unreachable case by exiting the loop early. Both approaches are valid and produce the same result.

Let us trace through [2,3,1,1,4]. Start with maxReach = 0. At index 0, nums[0] = 2, so maxReach = max(0, 0+2) = 2. At index 1, nums[1] = 3, so maxReach = max(2, 1+3) = 4. Since maxReach (4) is already >= last index (4), return true.

Now trace [3,2,1,0,4]. Start with maxReach = 0. At index 0, maxReach = max(0, 0+3) = 3. At index 1, maxReach = max(3, 1+2) = 3. At index 2, maxReach = max(3, 2+1) = 3. At index 3, maxReach = max(3, 3+0) = 3. We never exceed index 3, so we cannot reach index 4. Return false.

The failing case is clear: every position reachable from index 0 through index 3 adds nothing beyond what index 0 already provided. The zero at index 3 creates an impassable barrier because maxReach stalls at exactly 3 and the target is index 4.

A single-element array always returns true because you are already at the last index. This is the simplest case and your solution should handle it without entering the loop or by passing through trivially.

If the first element is 0 and the array has more than one element, you can never leave index 0 — return false immediately. More broadly, any zero in the array is a potential trap, but it only blocks you if maxReach does not extend past it from an earlier index.

An array of all zeros except the first element, like [5,0,0,0,0,0], succeeds as long as the first element is large enough to reach the end. The zeros are irrelevant because you jump over them entirely from the starting position.

Jump Game is the textbook example of greedy reachability. The core lesson is that you do not need to enumerate every possible path when a single running maximum captures all the information you need. This principle applies whenever the problem asks whether something is reachable or coverable.

This same pattern forms the foundation for Jump Game II (#45), where you need the minimum number of jumps to reach the end. The key difference is that Jump Game II tracks when you must take a new jump, but the underlying reachability logic is identical.

Once you internalize the max reach array pattern, you will recognize it in problems about video stitching, interval coverage, and gas station circuits. Practice this problem until the single-variable greedy approach feels automatic, then review it periodically with YeetCode flashcards to keep the pattern fresh.