Where to start a delivery loop so the van never runs dry

Greedy choices and intervals Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
fuel = [4, 1, 2, 6, 3]
cost = [2, 5, 4, 1, 3]
start = tank = 0
for i in range(len(fuel)):
    tank += fuel[i] - cost[i]
    if tank < 0:
        start, tank = i + 1, 0
print(start, sum(fuel) >= sum(cost))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3 True

Right: the tank goes negative after stops 1 and 2, so the loop starts at stop 3, and the totals allow a full loop.

Each restart discards a stretch that could never contain a valid start, so one pass is enough.

Why not the others?
  • B 4 True. From stop 3 the tank stays non-negative, so there is no restart at 4.
  • C 0 True. Stop 0 has spare fuel, but the van runs dry leaving stop 1.

30-second answer

If total fuel is less than total cost, no start works. Otherwise walk once, keeping a running tank; whenever it drops below zero, no stop from the current start up to here can be a start, so restart from the next stop with an empty tank. The last restart point is the answer. O(n) time, O(1) memory.

Practise saying it · 45 s. No recording, just a timer

Explain the fuel-loop greedy.

Say your answer out loud, then check which of these points you covered:

  • Total check
  • Restart after a negative tank
  • O(n)

Deep dive

The skip is the key proof: any start inside a failed stretch fails even sooner.

Total fuel ≥ total cost guarantees the final candidate works.

Trying every start is O(n²).

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def loop_start(fuel: list[int], cost: list[int]) -> int:
    if sum(fuel) < sum(cost):
        return -1
    start = tank = 0
    for i, (got, spent) in enumerate(zip(fuel, cost)):
        tank += got - spent
        if tank < 0:  # no stop from start to i can begin the loop
            start, tank = i + 1, 0
    return start

Common mistakes

  • Restarting at the failure point itself instead of the next stop.
  • Skipping the total check, which returns a start even when none works.

Senior take & follow-ups

Explain why skipping a whole stretch is safe; that is the interview's real question.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why does total ≥ cost make the last candidate valid?

    Show hint

    The stretch before it had a negative sum, so the rest must cover it with a non-negative total.

  2. What if the van may start with some fuel?

    Show hint

    Add it to the first stop's fuel; the same scan works.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.