Skip to main content
Ace Hired
All coding problems

Jump Game II: Minimum Jumps

Mediumdynamic programmingGreedy interval expansion (BFS-style level counting)dynamic-programminggreedyarrays

Maintained by Vikas D, software engineer

You begin standing on index 0 of an integer array. The number sitting at your current index is a ceiling, not a fixed distance: from index i you may land on any index between i+1 and i+nums[i]. Smaller hops are always allowed, so a value of 4 lets you advance one, two, three, or four positions in a single move.

Your goal is to count the smallest number of moves that gets you onto the final index. The problem promises the end is always reachable, so you never have to worry about getting stuck or returning a sentinel for failure.

Because every move can cover a range of landing spots, the interesting question is not whether you can finish but how to finish in as few hops as possible. Greedily reaching as far as you can with each jump turns out to be optimal, which is why this problem rewards thinking in terms of reachable windows rather than individual cells.

Examples

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

From index 0 you can reach index 1 or 2. Landing on index 1 (value 3) then lets you reach index 4 directly. Two jumps total. Going through index 2 would need a third jump, so two is the minimum.

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

The zero at index 2 is a dead spot, but you never have to step on it. Jump 0 to 1, then 1 to 4 using the stride of 3. The greedy window from the first jump already covers indices 1 through 2, and index 1 extends the reach all the way to the end.

Input: nums = [1, 1, 1, 1]
Output: 3

Every value is 1, so each jump advances exactly one position. Reaching index 3 from index 0 takes three single steps.

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • The last index is always reachable from index 0.
  • A single-element array needs zero jumps.

Visible test cases

  • jump([2,3,1,1,4]) == 2
  • jump([2,3,0,1,4]) == 2
  • jump([1,2,3]) == 2
  • jump([1]) == 0
  • jump([1,1,1,1]) == 3

Hints

Hint 1

An element does not force you to jump its full value. From index i you can land anywhere in the range i+1 to i+nums[i], so think about the set of indices each jump unlocks rather than one destination.

Hint 2

Process the array left to right and track the farthest index you could reach if you take one more jump. The current jump covers a contiguous window of indices; you only spend a new jump when you step past the right edge of that window.

Hint 3

Keep three counters: the boundary of the current jump's window, the farthest index reachable so far, and the jump count. Increment jumps the moment your scan index hits the window boundary, then extend the boundary to the farthest reachable index.

Loading the editor...

Approaches

Breadth-first level expansion

Time O(n) · Space O(1)

Treat indices as nodes and each jump as moving one level deeper in a BFS. Every level is the set of indices reachable with the same number of jumps, so the level at which the last index first appears is the answer.

  1. Maintain the inclusive bounds [left, right] of the current level, starting at [0, 0].
  2. For each index in the current level, compute the farthest index it can reach.
  3. The next level spans from right+1 to that farthest value; increment the jump count by one.
  4. Stop as soon as the level boundary covers or passes the last index.

Greedy window scan (optimal)

Time O(n) · Space O(1)

Walk through the array once while tracking the farthest reachable index. The current jump owns a window of indices; the instant your scan reaches the window's right edge you must have spent a jump, so bump the count and slide the window out to the farthest point seen so far.

  1. Initialise jumps, currentEnd, and farthest to 0.
  2. Iterate i from 0 up to but not including the last index.
  3. Set farthest to the maximum of itself and i + nums[i].
  4. When i equals currentEnd, increment jumps and set currentEnd to farthest.
  5. Return jumps after the loop; stopping before the last index avoids counting a phantom extra jump on arrival.

Common mistakes

  • Looping all the way to the last index instead of stopping one short. When i reaches the final position you can overcount by one jump, since arriving at the end should not trigger a new window.
  • Assuming you must jump exactly nums[i] steps. The value is a maximum, so a greedy that only considers the single farthest landing per cell misses that every shorter hop inside the range is also free.
  • Treating a 0 as an automatic failure. A zero only blocks you if you are forced to stand on it; the reachability guarantee plus the greedy window usually carries you over it.
  • Returning the farthest reach or the window boundary instead of the jump count. The answer is how many times you slid the window, not how far you got.

Follow-up variations

  • What changes if reaching the end is not guaranteed and you must return -1 when it is impossible?
  • How would you reconstruct one actual sequence of indices that achieves the minimum number of jumps, not just the count?
  • Suppose jumping from index i costs nums[i] coins rather than one jump. Now you want the cheapest path, not the fewest hops. Does the greedy still hold?
  • If you could also jump backward, how would the approach need to change?

Recommended problems

Build the rest of your prep