Jump Game II

The problem

You start on position 0 of nums. Each number is the longest jump forward you may make from its position, and any shorter jump is allowed too. Return the smallest number of jumps that takes you to the last position. The last position can always be reached. If the list has one number you are already there, so the answer is 0.

What to write

function solve(nums: number[]): number

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

Output
2

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

Output
2

Constraints

The last index is guaranteed reachable.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The last position can always be reached, so the question is never whether you arrive, only how few jumps you need. Any shorter jump is allowed, and jumps only go forward. A list with one number needs 0 jumps.

2. Hint 2: Ask a smaller question

   In 2, 3, 1, 1, 4, which positions can you stand on after one jump? Which further positions does a second jump open up? Write both groups down. What do you notice about the shape of each group, and which group holds the last position?

3. Hint 3: Name the pattern

   The positions that need one jump form an unbroken stretch, and so do those that need two, and so on. So count stretches. The next stretch ends at the farthest spot that any position of the current stretch can jump to. Always claiming the farthest reach is a greedy choice: reaching farther never loses you an option. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   At the top of each round of the loop, the jumps counted are the fewest that reach the position the loop is on, and you know the last position those jumps reach. The farthest spot noted is the best landing spot of one more jump from any position visited so far.

5. Hint 5: Sketch the pseudocode

   end = 0, far = 0, jumps = 0. For each position i with number x, except the last position: far = the larger of far and i + x. If i equals end: add 1 to jumps and set end = far. After the loop, return jumps.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Scan all positions reachable with the current jump count. When that layer ends, advance to its farthest reachable boundary.

The slow way

Try every path: from each position try every jump length the number allows, count the jumps of each path that arrives, and keep the smallest count. It is correct, but when every number is large enough to reach the end, one more number doubles the work: 8 visits for 4 numbers, over a million for 21.

The insight

The positions you can reach with at most a given number of jumps form an unbroken stretch that starts at position 0, because shorter jumps are allowed. So there is no need to follow paths. Ask where the stretch for 0 jumps ends, then for 1 jump, then for 2, and stop when a stretch takes in the last position. That count is the fewest jumps.

Step by step

1. Start with 0 jumps, which reach position 0 and no farther. Three numbers are kept: the jumps counted, the last position those jumps can reach, and the farthest spot one more jump could land on. Before any jump, the count is 0 and both positions are 0.
2. Visit every position except the last one. The last position is where you want to arrive, not a place to jump from. Visiting it would count a jump too many whenever the reach ends exactly there.
3. Note the farthest spot that one more jump could land on. The next jump may start from any position the counted jumps reach. The longest jump from this position lands on the position plus its number, and the largest of those spots is where the next jump's reach will end.
4. This is the last position the counted jumps reach: count one more. The loop is about to move on to positions that the counted jumps cannot reach, and the last position is still ahead. So one more jump is needed, whichever path you take.
5. With that jump you reach as far as the farthest spot noted. The extra jump may start from any position visited so far, so it can land anywhere up to the farthest spot noted. Claiming all of that is safe: a longer reach can do everything a shorter one can.
6. Return the number of jumps counted. Each jump was counted only when positions ahead could not be reached without one more, and each reach went as far as possible. So the count is the fewest jumps that arrive at the last position.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start with 0 jumps, which reach position 0 and no farther
  let end = 0,
    farthest = 0,
    jumps = 0;
  // 2. Visit every position except the last one
  for (let i = 0; i < nums.length - 1; i++) {
    // 3. Note the farthest spot that one more jump could land on
    farthest = Math.max(farthest, i + nums[i]);
    // 4. This is the last position the counted jumps reach: count one more
    if (i === end) {
      jumps++;
      // 5. With that jump you reach as far as the farthest spot noted
      end = farthest;
    }
  }
  // 6. Return the number of jumps counted
  return jumps;
}

function solve(nums: number[]): number {
  // 1. Start with 0 jumps, which reach position 0 and no farther
  let end = 0,
    farthest = 0,
    jumps = 0;
  // 2. Visit every position except the last one
  for (let i = 0; i < nums.length - 1; i++) {
    // 3. Note the farthest spot that one more jump could land on
    farthest = Math.max(farthest, i + nums[i]);
    // 4. This is the last position the counted jumps reach: count one more
    if (i === end) {
      jumps++;
      // 5. With that jump you reach as far as the farthest spot noted
      end = farthest;
    }
  }
  // 6. Return the number of jumps counted
  return jumps;
}

def solve(nums):
    # 1. Start with 0 jumps, which reach position 0 and no farther
    end = farthest = jumps = 0
    # 2. Visit every position except the last one
    for i in range(len(nums) - 1):
        # 3. Note the farthest spot that one more jump could land on
        farthest = max(farthest, i + nums[i])
        # 4. This is the last position the counted jumps reach: count one more
        if i == end:
            jumps += 1
            # 5. With that jump you reach as far as the farthest spot noted
            end = farthest
    # 6. Return the number of jumps counted
    return jumps

Example 2, traced

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

Output
2

Why it works

Reaching farther never costs anything: a stretch that ends later contains every position of one that ends earlier, so it offers every jump the shorter one offers. So always taking the farthest reach and never reconsidering, the greedy choice, is safe. A jump is counted only when the positions ahead cannot be reached without it, and each stretch ends as far as possible, so no smaller count can arrive.

Time and space

Time O(n), extra space O(1). The loop makes one pass: it visits each position except the last once, with one comparison to update the farthest spot and one check for the end of the reach, so the time is O(n). Three numbers are stored, whatever the length of the list: O(1) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Stop the loop before the last position. If it is visited too, an extra jump is counted whenever the reach ends exactly there: example 1 returns 3, not 2, and a list with one number returns 1, not 0.
• Do not always take the longest jump. In example 1 that goes from position 0 to 2, then to 3, then to 4: three jumps. The short jump to position 1 is better: one jump from there reaches the end.
• If you choose each landing spot yourself, compare position plus number, not the number. In 3, 3, 1, 2, 1, 1, going through the 3 at position 1 takes three jumps, and through the 2 at position 3 only two.

Pattern

Greedy choice. Builds on Jump Game.

Keep going