Jump Game II

1. The obvious way

   DP: minimum jumps to each position, checking all earlier positions: O(n²).

2. The key insight

   Track the end of the current zone (zone_end) and the farthest you can reach from anywhere in this zone (farthest). Walk positions; update farthest. When you arrive at zone_end, take a jump: jumps + 1 and the new zone ends at farthest. Stop before the last position.

3. The algorithm
   1. jumps = 0, zone_end = 0, farthest = 0.
   2. For each position except the last: farthest = max(farthest, position + leap).
   3. Position == zone_end? Take a jump: jumps + 1, zone_end = farthest.
   4. Return jumps.

Watch it run

jumps = 1, zone ends at 2

def jump(nums):
    jumps = 0
    zone_end = 0                                       # last position reachable with 'jumps' jumps
    farthest = 0                                       # farthest reachable with one more jump
    for position in range(len(nums) - 1):
        farthest = max(farthest, position + nums[position])
        if position == zone_end:
            jumps += 1                                 # we must jump to go beyond this zone
            zone_end = farthest
    return jumps

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.