Jump Game

The problem

You start on the first position of nums, position 0. Each number is the longest jump forward you may make from its position, and any shorter jump is allowed too. A 0 means you cannot move on from there. Return true if some sequence of jumps takes you to the last position, and false if none does. If the list has one number you are already there, so the answer is true.

What to write

function solve(nums: number[]): boolean

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

Output
true

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

Output
false

Constraints

1–10,000 nonnegative integers, each ≤ 10,000.

Hints

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

1. Hint 1: Use the constraints

   Each number is a maximum, so every shorter jump is allowed as well. No number is negative, so you never move backward. That makes a 0 the only place where you can get stuck, and only when no earlier position can jump over it.

2. Hint 2: Ask a smaller question

   In 3, 2, 1, 0, 4, work out, for each of the first four positions, the farthest position that one jump from it can land on. What do you notice? Would the answer change if position 1 held a 3 instead of a 2?

3. Hint 3: Name the pattern

   If you can reach a position, you can reach every position before it too, because shorter jumps are allowed. So one number sums up all the paths: the farthest position reachable so far. Let each position you pass push that number forward. Keeping only the best reach, and never looking back, is a greedy choice. Read the lesson on greedy choice.

4. Hint 4: State the invariant

   At the start the farthest reach is position 0. When the loop arrives at a later position, the farthest reach is the farthest landing spot of any jump from the positions before it. Every position up to the farthest reach can be reached. So if the loop arrives beyond the farthest reach, no jump can get there.

5. Hint 5: Sketch the pseudocode

   far = 0. For each position i with number x, from left to right: if i is greater than far, return false. Otherwise far = the larger of far and i + x. If the loop finishes, return true.

Solution

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

Approach

Track the farthest reachable position. If the scan reaches a position beyond that boundary, it cannot continue; otherwise extend the boundary.

The slow way

From position 0, try every jump length the number allows, and from each landing spot every length again, until one path arrives or all have failed. Nothing is missed, but a position can be visited again for every path that leads to it. On lists that count down to 0 like example 2, one more number doubles the work: 8 visits for 5 numbers, over a million for 22.

The insight

Shorter jumps are allowed, so if you can reach a position you can reach every position before it. The positions you can reach form one unbroken stretch that starts at position 0, and all you need to know is where the stretch ends. Every position inside the stretch gets one chance to push that end forward.

Step by step

1. Remember the farthest position you can reach: at first, position 0. You stand on position 0 before any jump, so it is the only position known to be reachable. This one number will stand in for every path you could take.
2. Visit the positions from left to right. Jumps only go forward. So when the loop arrives at a position, all the positions that could jump there have already been handled.
3. This position is beyond the farthest reach: return false. No earlier position has a jump long enough to land here, and jumps never go backward. So this position cannot be reached, and neither can any position after it. The last position is one of them.
4. Otherwise a jump from here may push the farthest reach forward. The longest jump from here lands on this position plus its number. The farthest reach keeps the larger of the old value and that spot, so a short jump never pulls the reach back.
5. No position was out of reach: return true. The loop passed every position without finding one beyond the farthest reach. That includes the last position, so some sequence of jumps arrives there.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Remember the farthest position you can reach: at first, position 0
  let far = 0;
  // 2. Visit the positions from left to right
  for (let i = 0; i < nums.length; i++) {
    // 3. This position is beyond the farthest reach: return false
    if (i > far) return false;
    // 4. Otherwise a jump from here may push the farthest reach forward
    far = Math.max(far, i + nums[i]);
  }
  // 5. No position was out of reach: return true
  return true;
}

function solve(nums: number[]): boolean {
  // 1. Remember the farthest position you can reach: at first, position 0
  let far = 0;
  // 2. Visit the positions from left to right
  for (let i = 0; i < nums.length; i++) {
    // 3. This position is beyond the farthest reach: return false
    if (i > far) return false;
    // 4. Otherwise a jump from here may push the farthest reach forward
    far = Math.max(far, i + nums[i]);
  }
  // 5. No position was out of reach: return true
  return true;
}

def solve(nums):
    # 1. Remember the farthest position you can reach: at first, position 0
    far = 0
    # 2. Visit the positions from left to right
    for i, jump in enumerate(nums):
        # 3. This position is beyond the farthest reach: return false
        if i > far:
            return False
        # 4. Otherwise a jump from here may push the farthest reach forward
        far = max(far, i + jump)
    # 5. No position was out of reach: return true
    return True

Example 2, traced

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

Output
false

Why it works

The farthest reach was set by a position you can reach, and from there a shorter jump lands on any spot up to the reach. So every position the loop passes is reachable, and true is right. A position beyond the reach is out of range of every earlier position, so false is right. Keeping one number and never looking back, the greedy choice, loses nothing.

Time and space

Time O(n), extra space O(1). The loop makes one pass: it visits each of the n positions at most once and does one comparison and one update for each, so the time is O(n). One number is stored, the farthest reach, 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

• Do not follow a single path of longest jumps. In 2, 2, 0, 1 the longest jump from position 0 lands on the 0 and is stuck, while the shorter jump to position 1 gets through.
• Check a position before you use its number. If the farthest reach is raised first, a position that cannot be reached vouches for itself: in example 2 position 4 lifts the reach to 8, and true is returned.
• The longest jump lands on the position plus the number, not on the number. Comparing the farthest reach with the number alone returns false for example 1, where the answer is true.

Pattern

Greedy choice. Builds on Maximum Subarray.

Keep going