medium

Jump Game II

Find the minimum number of jumps needed to reach the last position of an array.

1. Define the problem

Jump Game II

You start at the first position of an array. The number at each position is the furthest you can jump forward from there — you may jump any distance up to that number. Return the smallest number of jumps needed to land on the last position. You are told the last position is always reachable. Do not decide where to land each time. Instead, walk forward and keep track of the furthest position anything in the current jump can reach . When you walk past the end of the current jump , you have to spend another jump, and the new reach becomes the furthest you spotted along the way.

Constraints

  • 1 ≤ nums.length ≤ 104
  • 0 ≤ numsi ≤ 1000
  • The last position is always reachable
  • If the array has only one position the answer is 0

Example

Inputnums = [2, 3, 1, 1, 4]
Output2

Explanation Jump from index 0 to index 1, then from index 1 straight to index 4. Two jumps is the fewest possible.

2. Know the words first

In plain terms

Greedy
Taking the best-looking option at each point and never going back to reconsider. It only works when you can show the local best is also the overall best, which is the case here.
Reach
The furthest index you could land on from a given position. From index i with the number n, the reach is i + n.
End of the current jump
The last index you can still get to without spending another jump. Crossing it is what forces the jump count up by one.
3. Visualize the solution

Walk forward and count a jump only when the current reach runs out

Walk forward and count a jump only when the current reach runs out
Statusjump 1

At index 0 you can reach index 2, and spending the first jump is unavoidable.

What happens in this step

i = 0, nums[0] = 2
farthest = 0 + 2 = 2
i is the end of the current jump, so jumps = 1 and the new end is 2

The box covers indexes 0 to 2: anywhere inside it is reachable with this one jump.
Step 1 of 5

Steps to visualize

  1. The row is the array; each cell shows how far you may jump from that position.
  2. The box runs from where you are standing to the furthest position reachable so far.
  3. At each position work out position + value and keep the largest you have seen.
  4. While you are still inside the current jump, no jump is counted.
  5. The moment you step onto the end of the current jump, add one to the count.
  6. The new end becomes the furthest reach spotted while crossing the old one.
  7. The last position never needs checking, because arriving there is the goal.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walk forward and count a jump only when the current reach runs out
Statusjump 1

At index 0 you can reach index 2, and spending the first jump is unavoidable.

What happens in this step

i = 0, nums[0] = 2
farthest = 0 + 2 = 2
i is the end of the current jump, so jumps = 1 and the new end is 2

The box covers indexes 0 to 2: anywhere inside it is reachable with this one jump.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < nums.length - 1; i += 1) {
    if (i + nums[i] > farthest) {
      farthest = i + nums[i];
    }

    if (i === currentEnd) {
      jumps += 1;
      currentEnd = farthest;
    }
  }

  return jumps;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
nums = [2, 3, 1, 1, 4]2example from the description
nums = [2, 3, 0, 1, 4]2a position you must jump over because it goes nowhere
nums = [0]0starting on the last position, so no jumps at all
nums = [1, 2]1smallest array that needs a jump
nums = [1, 1, 1, 1]3worst case where every jump moves one position
nums = [5, 1, 1, 1, 1]1the first position reaches the end on its own

Keep reading