Jump Game, Gas Station and Reach Problems

28 min · Intermediate

Some greedy problems need no sorting at all. You walk the input once and keep one number, such as the farthest place you can reach or a running balance. If that number breaks, the answer changes. These passes cost O(n) time and O(1) space.

Jump game: keep the farthest reach

The farthest reach is the largest index you can get to using the cells seen so far. Each cell i raises it to at least i plus the jump length at i.

Each cell holds the longest jump you may make from it. Can you get from the first cell to the last? Walk forward and keep the farthest index reachable so far. If you stand on a cell beyond it, you are stuck.

Python

1def can_reach_end(jumps):2    reach = 03    for i, step in enumerate(jumps):4        if i > reach:5            return False6        reach = max(reach, i + step)7    return True8
9
10print(can_reach_end([2, 3, 1, 1, 4]), can_reach_end([3, 2, 1, 0, 4]))

Example 1 · Brute force jump game: try every jump

Python

1def can_reach(jumps, i=0, seen=None):2    seen = set() if seen is None else seen3    if i >= len(jumps) - 1:4        return True5    if i in seen:6        return False7    seen.add(i)8    return any(can_reach(jumps, i + k, seen) for k in range(1, jumps[i] + 1))9
10
11print(can_reach([2, 3, 1, 1, 4]), can_reach([3, 2, 1, 0, 4]))

Output

True False

What this code does

Without the seen set this would be exponential. With it, the search is still O(n squared) time because each cell tries many jumps.
The greedy reach gives the same answers in O(n).

Example 2 · Greedy reach shown step by step

Python

1jumps = [3, 2, 1, 0, 4]2reach = 03for i, step in enumerate(jumps):4    if i > reach:5        print("stuck at", i)6        break7    reach = max(reach, i + step)8    print(i, reach)

Output

0 3
1 3
2 3
3 3
stuck at 4

What this code does

The reach grows to 3 and then stays at 3. Index 4 is past it, so you are stuck there.
Index 3 holds a jump of 0, so it adds nothing.

One pass gives O(n) time and O(1) space. A recursive try-everything version would be exponential.

Minimum jumps: grow the window level by level

A level is the group of cells reachable with the same number of jumps. Greedy moves from one level to the next by jumping to the farthest cell the current level can reach.

Now count the fewest jumps. Think of levels: all cells reachable with one jump, then with two, and so on. When you pass the end of the current level, you must jump once more, to the farthest cell seen.

Python

1def min_jumps(jumps):2    count = level_end = reach = 03    for i in range(len(jumps) - 1):4        reach = max(reach, i + jumps[i])5        if i == level_end:6            count += 17            level_end = reach8    return count9
10
11print(min_jumps([2, 3, 1, 1, 4]))

Example 3 · Minimum jumps with levels

Python

1jumps = [2, 3, 1, 1, 4]2count = level_end = reach = 03for i in range(len(jumps) - 1):4    reach = max(reach, i + jumps[i])5    if i == level_end:6        count += 17        level_end = reach8print(count)

Output

What this code does

The first jump from index 0 reaches index 2 at most. At index 2 the best reach is 4, so the second jump finishes.
The answer is 2 jumps.

It assumes the end can be reached. Time is O(n) and space is O(1), while a dynamic programming table would be O(n squared).

Gas station: a running total that resets

A running total is a sum that is updated one item at a time as you scan. Greedy reach problems use it to detect the moment a plan stops working.

Stations sit on a ring. Station i gives gas[i] and the trip to the next costs cost[i]. Find a start from which you can drive the full ring. If the total gas is less than the total cost, none exists. Otherwise, restart after any station where the tank goes below zero.

Python

1def start_station(gas, cost):2    if sum(gas) < sum(cost):3        return -14    start = tank = 05    for i in range(len(gas)):6        tank += gas[i] - cost[i]7        if tank < 0:8            start, tank = i + 1, 09    return start10
11
12print(start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

Example 4 · Gas station with the tank shown

Python

1gas = [1, 2, 3, 4, 5]2cost = [3, 4, 5, 1, 2]3start = tank = 04for i in range(len(gas)):5    tank += gas[i] - cost[i]6    print(i, tank)7    if tank < 0:8        start, tank = i + 1, 09print("start", start)

Output

0 -2
1 -2
2 -2
3 3
4 6
start 3

What this code does

The tank is negative at stations 0, 1 and 2, so the start moves each time. From station 3 it stays at or above zero.
The total gas, 15, is at least the total cost, 15, so station 3 works.

If a start fails at station i, every start between it and i fails too, so the next try is i + 1. That makes the loop O(n).

The same shape in trades and subarrays

Best single trade keeps the lowest price seen so far and the best gain. Maximum subarray keeps the best sum ending here and restarts when it turns negative. Both carry one value forward through a single loop.

Python

1def best_trade(prices):2    low, gain = prices[0], 03    for price in prices[1:]:4        low = min(low, price)5        gain = max(gain, price - low)6    return gain7
8
9print(best_trade([7, 1, 5, 3, 6, 4]))

Example 5 · Maximum subarray: restart when the sum turns negative

Python

1marks = [-2, 1, -3, 4, -1, 2, 1, -5, 4]2best = here = marks[0]3for value in marks[1:]:4    here = max(value, here + value)5    best = max(best, here)6print(best)

Output

What this code does

here is the best sum of a block ending at this value. A negative running sum is dropped, because starting fresh is better.
The best block is 4, -1, 2, 1, which adds up to 6.

A nested loop over every buy and sell day is O(n squared). The single pass is O(n) time and O(1) space.

Next step

Check your understanding

10 quick questions

Jump game: keep the farthest reach

The farthest reach is the largest index you can get to using the cells seen so far. Each cell i raises it to at least i plus the jump length at i.

1def can_reach_end(jumps):2 reach = 03 for i, step in enumerate(jumps):4 if i > reach:5 return False6 reach = max(reach, i + step)7 return True8 9 10print(can_reach_end([2, 3, 1, 1, 4]), can_reach_end([3, 2, 1, 0, 4]))

1def can_reach(jumps, i=0, seen=None):2 seen = set() if seen is None else seen3 if i >= len(jumps) - 1:4 return True5 if i in seen:6 return False7 seen.add(i)8 return any(can_reach(jumps, i + k, seen) for k in range(1, jumps[i] + 1))9 10 11print(can_reach([2, 3, 1, 1, 4]), can_reach([3, 2, 1, 0, 4]))

Minimum jumps: grow the window level by level

A level is the group of cells reachable with the same number of jumps. Greedy moves from one level to the next by jumping to the farthest cell the current level can reach.

1def min_jumps(jumps):2 count = level_end = reach = 03 for i in range(len(jumps) - 1):4 reach = max(reach, i + jumps[i])5 if i == level_end:6 count += 17 level_end = reach8 return count9 10 11print(min_jumps([2, 3, 1, 1, 4]))

1jumps = [2, 3, 1, 1, 4]2count = level_end = reach = 03for i in range(len(jumps) - 1):4 reach = max(reach, i + jumps[i])5 if i == level_end:6 count += 17 level_end = reach8print(count)

Gas station: a running total that resets

A running total is a sum that is updated one item at a time as you scan. Greedy reach problems use it to detect the moment a plan stops working.

1def start_station(gas, cost):2 if sum(gas) < sum(cost):3 return -14 start = tank = 05 for i in range(len(gas)):6 tank += gas[i] - cost[i]7 if tank < 0:8 start, tank = i + 1, 09 return start10 11 12print(start_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))

1gas = [1, 2, 3, 4, 5]2cost = [3, 4, 5, 1, 2]3start = tank = 04for i in range(len(gas)):5 tank += gas[i] - cost[i]6 print(i, tank)7 if tank < 0:8 start, tank = i + 1, 09print("start", start)

1def best_trade(prices):2 low, gain = prices[0], 03 for price in prices[1:]:4 low = min(low, price)5 gain = max(gain, price - low)6 return gain7 8 9print(best_trade([7, 1, 5, 3, 6, 4]))