Greedy

Jump Game / Reach Maximization

Track the farthest index reachable from current position. At each step, greedily extend the maximum reach. If current position exceeds max reach, return false.

You are given an array of non-negative integers where each element represents the maximum number of positions you can jump forward from that index. Starting at index 0, can you reach the last index? This is Jump Game I, one of the cleanest examples of a problem where greedy completely replaces dynamic programming, not as an optimization, but because the problem structure makes DP unnecessary.

Why DP and BFS are overkill

The brute-force approach is to try every possible jump from every position. You could define dp[i] as "can I reach index i?" and fill it by checking all earlier positions that could jump to i. That is $O(n^2)$ time. You could also model the array as a graph where index i has edges to indices i+1 through i+nums[i], then run BFS. That is also $O(n^2)$ in the worst case because of the number of edges.

But notice something: you do not care about which specific path reaches a position. You only care whether some path reaches it. And if position j is reachable and j + nums[j] >= i, then i is reachable. The identity of the path does not matter, only the farthest point any path has reached. This means a single variable tracking the maximum reachable index is sufficient.

The farthest-reach invariant

The algorithm maintains one variable, farthest, which represents the farthest index reachable from any position you have visited so far. Scan left to right:

At each index i, first check: is i > farthest? If so, you cannot be standing here, because no previous position could reach this far. Return false.
Otherwise, update farthest = max(farthest, i + nums[i]). The current position extends your reach to i + nums[i], which might be farther than anything you have seen before.
If you finish the loop without failing the check, return true.

The invariant is simple: after processing index i, farthest equals the maximum index reachable using any combination of jumps from indices 0 through i. Because you process indices in order and skip none (as long as they are reachable), you never miss a better jump.

Worked example: Jump Game I

Consider nums = [2, 3, 1, 1, 4]. We want to reach index 4.

i=0: farthest = 0. Is 0 > 0? No. Update farthest = max(0, 0+2) = 2.
i=1: farthest = 2. Is 1 > 2? No. Update farthest = max(2, 1+3) = 4.
i=2: farthest = 4. Is 2 > 4? No. Update farthest = max(4, 2+1) = 4.
i=3: farthest = 4. Is 3 > 4? No. Update farthest = max(4, 3+1) = 4.
i=4: farthest = 4. Is 4 > 4? No. Update farthest = max(4, 4+4) = 8.

Loop ends. Return true. We can reach the end.

Now consider nums = [3, 2, 1, 0, 4]. We want to reach index 4.

i=0: farthest = max(0, 0+3) = 3.
i=1: farthest = max(3, 1+2) = 3.
i=2: farthest = max(3, 2+1) = 3.
i=3: farthest = max(3, 3+0) = 3.
i=4: Is 4 > 3? Yes. Return false.

Index 3 has a jump length of 0, and no earlier index can jump past it. We are stuck.

Code: Jump Game I

1

2

3

4

5

6

7

def canJump(nums):
    farthest = 0
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    return True

$O(n)$ time, $O(1)$ space. That is the entire solution.

Jump Game II: minimum number of jumps

In LeetCode 45, you are guaranteed that the last index is reachable, and you need to find the minimum number of jumps to get there. This is where things get more interesting.

The BFS-without-a-queue insight

Think of the problem as BFS on an implicit graph. From index 0, you can reach indices 1 through nums[0] in one jump. From any of those indices, you can reach further indices in two jumps. And so on. Each "level" of BFS corresponds to one jump.

In standard BFS you use a queue and process nodes level by level. Here, you do not need a queue because the levels form contiguous ranges. If the current level covers indices from current_start to current_end, the next level covers indices from current_end + 1 to next_farthest, where next_farthest is the maximum of i + nums[i] for all i in the current level.

You can simplify this to two variables:

current_end: the last index reachable with the current number of jumps. This is the "level boundary."
farthest: the farthest index reachable from any index in the current level.

When your scan index i crosses current_end, you have exhausted the current level. Increment the jump counter and set current_end = farthest.

The level boundary concept

The variable current_end is the key to the algorithm. It marks where the "wave front" of the current jump ends. Every index up to and including current_end is reachable in jumps jumps. Every index from current_end + 1 to farthest requires at least one more jump.

When i passes current_end, you are entering the next level, the positions that require one additional jump. At that moment, you know exactly how far the next level extends (it is farthest), so you update the boundary and increment the count.

Walked example: minimum jumps on [2, 3, 1, 1, 4]

Target: index 4. Initialize jumps = 0, current_end = 0, farthest = 0.

i=0: farthest = max(0, 0+2) = 2. Now i == current_end (both 0), so we must jump. jumps = 1, current_end = 2.
i=1: farthest = max(2, 1+3) = 4. i < current_end, continue.
i=2: farthest = max(4, 2+1) = 4. Now i == current_end (both 2), so we must jump. jumps = 2, current_end = 4.
i=3: farthest = max(4, 3+1) = 4. i < current_end, continue.
We don't need to process i=4 because current_end already covers it.

Answer: 2 jumps. The path is 0 -> 1 -> 4 (jump 2 to index 1, then jump 3 to index 4).

Code: Jump Game II

def jump(nums):
    jumps = 0
    current_end = 0
    farthest = 0
    for i in range(len(nums) - 1):  # don't process last index
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

Note the loop runs to len(nums) - 1, not len(nums). This is important: if you include the last index, you might incorrectly increment jumps one extra time when current_end happens to equal the last index. You are already there, so no jump is needed.

$O(n)$ time, $O(1)$ space.

Why the greedy works

The correctness argument is that you never benefit from a shorter jump when a longer one is available from the same level. Suppose you are at level k and two positions are available: one that reaches index 7 and one that reaches index 10. Choosing the one that reaches 10 can only help, because every index reachable from the position-7 choice is also reachable from some position in the range up to 10. By maximizing farthest at each level, you make the next level as wide as possible, which means you need fewer levels overall.

More formally, the greedy produces a sequence of level boundaries. If any optimal solution has a narrower level at step k, it would need at least as many total levels, because a narrower level k implies a narrower or equal level k+1, and so on. The greedy maximizes every level, so it minimizes the total number.

Common bugs

Off-by-one on the level boundary. The loop in Jump Game II must iterate to len(nums) - 1, not len(nums). Processing the last index can cause a spurious extra jump when the boundary happens to land exactly on the second-to-last index.

Incrementing jumps at the wrong time. The jump increment must happen when i == current_end, not when farthest changes. The boundary crossing is what triggers a new jump. Updating farthest just tracks where the next boundary will be.

Forgetting the unreachable check in Jump Game I. If you skip the if i > farthest check, the algorithm will happily process unreachable indices and might incorrectly report true. For Jump Game II the problem guarantees reachability, so this check is unnecessary there, but for Jump Game I it is essential.

Confusing the two problems' loop bounds. Jump Game I loops over all indices (to check reachability of the last one). Jump Game II loops over all indices except the last (because reaching the last index does not require a jump from the last index).

Complexity summary

Problem	Time	Space
Jump Game I (can reach?)	$O(n)$	$O(1)$
Jump Game II (min jumps)	$O(n)$	$O(1)$
Brute-force DP approach	$O(n^2)$	$O(n)$

The jump game problems are a textbook case of greedy dominating DP. The structure of the problem, namely a linear scan, unidirectional movement, and a single "farthest reach" that captures all necessary state, means that the greedy approach is not just faster but conceptually simpler. Once you internalize the farthest-reach invariant, both variants become five-line solutions.

Recognizing this pattern

You're probably looking at jump-game reach maximization when:

You have an array where each entry encodes a maximum step length (or coverage range) from that index, and movement is unidirectional.
The question is "can you reach the end," "minimum jumps to reach the end," or "minimum items to cover a span," not "find the actual path."
The state needed to decide the next move collapses to a single number: the farthest index reachable so far.
BFS-style level expansion would work but feels wasteful: you don't actually need a queue, only the current frontier boundary.
Bidirectional movement, fixed jump destinations, or non-monotone reachability are absent; those break the greedy and push toward BFS/DFS.

Common templates:

Can-reach reachability scan: track farthest, return false the moment $i > farthest$ . Example: Jump Game.
Minimum jumps (BFS-as-greedy): track current_end and farthest, bump jump counter when $i$ hits the boundary. Example: Jump Game II.
Coverage / interval covering: sort by start, repeatedly extend by the interval with the farthest end inside the current frontier. Example: Video Stitching.
Circular surplus scan: track running fuel and reset start when it goes negative. Example: Gas Station.
Maximum-reach with a twist: variants like minimum taps or boats where each item has a range. Example: Minimum Number of Taps to Open to Water a Garden.