Skip to main content
DSA patterns

Jump Game II

mediumGreedy Must-doAmazonGoogleMeta

Problem statement

You start at index 0 of an array nums. The value at each index tells you how far you're allowed to jump forward from there — from index i you can land on any index from i + 1 up to i + nums[i], as long as you don't go past the end of the array.

Find the smallest number of jumps needed to reach the last index. You're guaranteed that the last index is always reachable.

Examples

Example 1

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

Output: 2

Explanation: Jump 1 step from index 0 to index 1, then 3 steps from index 1 straight to the last index — two jumps in total.

Example 2

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

Output: 2

Explanation: Index 2 holds a 0, which would be a dead end if you landed exactly there, but jumping from index 0 to index 1 and then to the last index still works in 2 jumps, skipping right over it.

Hints

Hint 1: At every index, you have a range of indices you could jump to next — the one that lets you jump the furthest afterward is usually worth picking, even if it isn't the furthest one on this jump alone.

Approach

Optimal: Greedy, range expansion

Intuition

You never actually need to decide, in advance, exactly which index to land on. Instead, track the furthest index reachable using every jump seen so far (farthest), and the furthest index the current jump is allowed to carry you to (currentEnd). As long as you're still inside the current jump's range, keep scanning and stretching farthest. The moment you reach the edge of what the current jump could reach, that means you must have taken another jump to get any further — so count it, and the new jump's reach becomes whatever farthest had grown to.

Steps

  1. Set farthest = 0, currentEnd = 0, and jumps = 0.
  2. Walk i from 0 up to (but not including) the last index — you never need to jump from the last index.
  3. At each i, update farthest = max(farthest, i + nums[i]).
  4. If i has reached currentEnd (the range of the current jump is used up), increment jumps and set currentEnd = farthest.
  5. Return jumps once the loop finishes.

Dry run

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

i farthest after update i == currentEnd? action jumps after
0 max(0, 0+2) = 2 yes (currentEnd starts at 0) take jump, currentEnd = 2 1
1 max(2, 1+3) = 4 no (currentEnd = 2) — 1
2 max(4, 2+1) = 4 yes (currentEnd = 2) take jump, currentEnd = 4 2
3 max(4, 3+1) = 4 no (currentEnd = 4) — 2

The loop stops before index 4 (the last index). Final answer: jumps = 2.

Edge cases: an array with one element never enters the loop (there's nothing before the last index to scan), so jumps stays 0.

Complexity

Time O(n) - one pass over the array; each index updates the farthest-reachable boundary exactly once.

Space O(1) - three counters, regardless of how long the array is.

class Solution:
    def jump(self, nums):
        n = len(nums)
        jumps = 0
        current_end = 0
        farthest = 0
        for i in range(n - 1):
            farthest = max(farthest, i + nums[i])
            if i == current_end:
                jumps += 1
                current_end = farthest
        return jumps


if __name__ == "__main__":
    print(Solution().jump([2, 3, 1, 1, 4]))
    print(Solution().jump([2, 3, 0, 1, 4]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "fewest jumps to reach the end," where each position caps how far you can jump from it
  • Idea: greedily expand the furthest index reachable within the current jump; take a new jump only once you've used up the current one's range
  • Cost: O(n) time, O(1) space (greedy); O(n^2) time, O(n) space for the bottom-up DP; exponential for plain recursion
  • Trap: stopping the loop at the last index instead of before it, which can count one extra, unneeded jump

Interview follow-ups

  • Return the actual sequence of indices used, not just the count of jumps.

    Store, alongside farthest, which index achieved that farthest reach at the moment you take each jump — that index is the one you "landed" on. Replaying those recorded indices after the loop finishes reconstructs one valid shortest path. This adds an O(n) array to remember the choices, but keeps the O(n) time.

  • What if each index also has a cost associated with jumping from it, and you want the cheapest path among all shortest ones?

    The pure greedy range-expansion trick stops being enough once jumps aren't all equal, because it only tracks reachability, not cost. This becomes a shortest-path problem on a graph where each index has an edge to everywhere it can reach — a 0-1 BFS or Dijkstra's algorithm over that graph finds the minimum-cost path in O(n log n) using a priority queue, since edge weights are non-negative.

Frequently asked questions

Because we're never committing to one specific landing index — we're expanding the set of indices reachable within the current jump count. Every index inside the current range gets looked at before we decide to take another jump, so farthest always reflects the true best possible reach for the next jump, not a guess. That means the jump count returned is provably the minimum, not just a good estimate.

Once you're standing on the last index, you're already done — there's nothing left to jump for. Including it in the loop would let farthest update past the array's bounds for no benefit, since the answer doesn't change once currentEnd already covers the last index.

It's a clean test of greedy reasoning under a constraint that looks like it needs backtracking at first glance — the same instinct used when planning the fewest hops through a chain of proxies, or the fewest batches needed to roll out a change across a set of hosts where each host can "reach" a limited number of others in one step.

Yes — a 0 only means you can't jump from that index. As long as some earlier index's range skips over it (the way index 1 skips over the 0 at index 2 in Example 2), the greedy tracking of farthest naturally routes around it without any special-case code.