Q3 - Minimum Charging Stops for an Electric Prime Truck

Scenario: Amazon Prime's delivery fleet has gone fully electric. A Prime truck runs a long route from the depot out to a customer target miles away. It rolls out with startFuel miles of charge in the battery, and 1 mile of charge moves it 1 mile.

Along the route are charging stations where the truck can recharge between stops. stations[i] = [position, charge] means there is a station position miles from the depot that adds charge miles of range to the battery (each station may be used at most once).

The truck also hauls refrigerated Prime cargo, so the route has mandatory cold-chain checkpoints. checkpoints[j] = [position, reserve] means that when the truck reaches position, it must arrive with at least reserve miles of charge still in the battery, the headroom the refrigeration unit needs to keep the cargo cold through the stop. The reserve is a floor it must meet on arrival; it is not consumed. Stations and checkpoints may be given in any order.

Task: Return the minimum number of charging stops the truck needs to reach target while meeting every checkpoint's reserve, or -1 if it cannot be done no matter what.

Input:  target = 100, startFuel = 10,
        stations = [[10, 60], [20, 30], [30, 30], [60, 40]],
        checkpoints = [[50, 70]]
Output: 3
Why: Without the checkpoint, 2 stops suffice (spend the 60, then the 40). But the cold-chain
        checkpoint at mile 50 demands >= 70 charge on arrival, i.e. the truck must be able to reach
        mile 50 + 70 = 120 from there. Meeting that forces a third stop: use the 60 and both 30s to
        reach mile 130 (80 charge to spare at mile 50), which also clears the target.

Input:  target = 60, startFuel = 40,
        stations = [[20, 30]], checkpoints = [[10, 25]]
Output: 1
Why: The checkpoint at mile 10 needs >= 25 charge; with 40 miles of charge the truck arrives
        carrying 30, so it clears for free. One stop at the mile-20 station (+30) then carries it to 60.

Input:  target = 100, startFuel = 10,
        stations = [[10, 60], [20, 30], [30, 30], [60, 40]],
        checkpoints = [[40, 95]]
Output: -1
Why: The checkpoint at mile 40 demands >= 95 charge (reach >= 135). The only stations before
        it are the 60 and the two 30s; even using all three the truck reaches just mile 130 < 135.
        Impossible, even though the target alone would be reachable in 2 stops.

Why the Obvious Greedy Fails

The two natural greedy rules both lose:

• "Stop at every station you pass." This minimizes risk, not stops. You will rack up far more stops than necessary; skipping small tanks should often be free.
• "Only stop when you are about to run dry, and take the nearest station." Closer is not better: a nearby station might offer 5 miles while one you just rolled past offered 60. Taking the small one can strand you a mile later, or leave you short at the next cold-chain checkpoint.

The trouble is that a good decision at mile 20 depends on stations you have not evaluated yet, on how far you ultimately need to go, and on reserve floors you must clear later. Committing to a stop at the moment you reach a station forces you to guess all of that. So do not.

Solution 1: A Dynamic-Programming Approach

Before the slick greedy, here is the approach a lot of people reach for when plain greedy fails. It is worth knowing because it is easy to reason about and easy to prove correct. Flip the question around: instead of "how few stops to reach target," ask "with exactly s stops, how far can I get?"

Let dp[s] be the farthest distance reachable using s charging stops. Start with dp[0] = startFuel. Now walk the road left to right, interleaving stations and checkpoints by position:

• At a station [pos, charge]: if you can already reach it with s stops (dp[s] >= pos), stopping there costs one more stop and buys range, so dp[s + 1] = max(dp[s + 1], dp[s] + charge).
• At a checkpoint [pos, reserve]: any stop-count whose reach falls short of pos + reserve cannot clear the reserve, so mark dp[s] blocked. Those plans are dead from here on.

The answer is the smallest s whose dp[s] is still alive and reaches target. The one subtlety: when folding in a station, iterate s downward, so a single station is never used twice in the same pass.

The two moves in code, folding a station and blocking a checkpoint, are the whole loop:

for pos, kind, value in events:            # stations and checkpoints, left to right
    if kind == 1:                          # a station: fold it in
        for s in range(folded, -1, -1):    # downward, so this station is used once
            if dp[s] >= pos:               # reachable with s stops?
                dp[s + 1] = max(dp[s + 1], dp[s] + value)
        folded += 1
    else:                                  # a checkpoint: kill plans that miss the reserve
        for s in range(folded + 1):
            if dp[s] < pos + value:        # cannot arrive carrying the reserve
                dp[s] = NEG

On Example 1 the array fills like this, and the checkpoint is what wipes the cheap plans out:

dp[s] = farthest reach with s stops   (target 100, start 10)

   init              [ 10,  -,  -,  -,  - ]
   station 10 (+60)  [ 10, 70,  -,  -,  - ]
   station 20 (+30)  [ 10, 70,100,  -,  - ]
   station 30 (+30)  [ 10, 70,100,130,  - ]
   checkpoint 50, need reach >= 120:
                     [  X,  X,  X,130,  - ]   dp[0..2] wiped, only dp[3] survives
   station 60 (+40)  [  X,  X,  X,130,170 ]

   first surviving dp[s] >= 100 is dp[3]  ->  answer 3 stops

Watch the dp array fill in on Example 1. Stations lift the reachable distances; then the checkpoint wipes out every stop-count that cannot meet its reserve, which is what pushes the answer up to 3:

1 / 7

# O((n + m) * n) time | O(n) space
def min_charging_stops(target, start_fuel, stations, checkpoints):
    stations = sorted(s for s in stations if s[0] < target)
    n = len(stations)
    NEG = float("-inf")
    dp = [start_fuel] + [NEG] * n              # dp[s] = farthest reachable with s stops
    events = sorted([(p, 1, c) for p, c in stations] +
                    [(p, 0, r) for p, r in checkpoints if p < target])   # tie: checkpoint (0) before station (1)
    folded = 0
    for pos, kind, value in events:
        if kind == 1:                          # fold a station in
            for s in range(folded, -1, -1):    # downward so it is used once
                if dp[s] != NEG and dp[s] >= pos:
                    dp[s + 1] = max(dp[s + 1], dp[s] + value)
            folded += 1
        else:                                  # a reserve checkpoint: block the weak entries
            for s in range(folded + 1):
                if dp[s] != NEG and dp[s] < pos + value:
                    dp[s] = NEG
    for s in range(n + 1):
        if dp[s] != NEG and dp[s] >= target:
            return s
    return -1

This is correct and runs in O((n + m) · n) time. In an interview it is a completely respectable answer to land first, and it is far easier to prove than the greedy. But Amazon will usually push for better, so here is how a heap gets it to O((n + m) log n).

The Key Insight: Recharge in Hindsight

Reframe a "stop" as something you apply retroactively. Drive forward freely, and every time you roll past a station, do not decide anything, just remember how much charge it could have given you. Keep all those passed-but-unused tanks in a max-heap.

When you would fall short, reach back and "use" the single biggest tank you have already driven past. That is always the most charge-efficient way to buy one more stop's worth of range, and because you only ever pull the largest available tank, you are guaranteed to use the fewest stops.

The reserve checkpoints add exactly one wrinkle: the thing you can "fall short of" is no longer only the target. Think of the route as a sequence of gates to clear in order:

• a station at pos is a gate that needs reach >= pos (you must roll up to it to bank it),
• a checkpoint at pos is a gate that needs reach >= pos + reserve (arrive carrying the reserve),
• the target is a gate that needs reach >= target.

Process the gates left to right, and whenever the current reach is short of a gate, pop the biggest banked tank (one stop) until you clear it. If the heap empties first, it is impossible.

We never "decided" to skip a tank; tanks simply stayed in the heap, unused, when they were not needed. The reserve checkpoint just forced us to spend more of them, sooner, to keep enough charge in reserve. That is the whole trick.

Solution 2: The Optimal Max-Heap Approach

Merge stations, checkpoints, and the target into one event stream sorted by position (with gates before stations on a tie, so a checkpoint is checked before banking a station at the same spot). Walk it once, banking each station's charge into a max-heap. At every gate, pop the largest banked tank, counting a stop, until the reach clears the gate. If the heap empties first, return -1.

The whole walk is one loop: at each gate, spend in hindsight until the reach clears it, then bank the current station.

for pos, kind, value in events:            # stations and gates, left to right
    need = pos + value if kind == 0 else pos   # gate wants pos + reserve; a station just pos
    while reach < need:                    # short of this gate: spend in hindsight
        if not banked:
            return -1
        reach += -heapq.heappop(banked)    # use the single biggest tank passed
        stops += 1
    if kind == 1:
        heapq.heappush(banked, -value)     # bank this station's charge

On Example 1 that plays out as follows, the reserve checkpoint is what forces the extra pops:

gates in order, reach starts at 10, banked is a max-heap of the tanks passed:

   station 10 (+60)   reach 10 >= 10        bank {60}
   station 20 (+30)   reach 10 < 20   ->  pop 60  (stop 1)  reach 70,  bank {30}
   station 30 (+30)   reach 70 >= 30        bank {30, 30}
   checkpoint 50, need reach >= 120:
        70  < 120  ->  pop 30  (stop 2)  reach 100
        100 < 120  ->  pop 30  (stop 3)  reach 130   cleared, 80 to spare
   station 60 (+40)   reach 130 >= 60       bank {40}
   target 100         reach 130 >= 100      done
   answer = 3 stops

Trace Example 1 (target = 100, startFuel = 10, checkpoint at mile 50 needing reach >= 120). Step through the truck driving, banking each tank it passes, and reaching back for the biggest only when a gate, the checkpoint reserve in particular, leaves it short:

1 / 7

# O((n + m) log n) time | O(n) space
import heapq

def min_charging_stops(target, start_fuel, stations, checkpoints):
    # kind 1 = station (bank charge), kind 0 = gate (checkpoint or target); tie: gates before stations.
    events = sorted([(p, 1, c) for p, c in stations if p < target] +
                    [(p, 0, r) for p, r in checkpoints if p < target] +
                    [(target, 0, 0)])
    reach, stops, banked = start_fuel, 0, []      # banked: max-heap of charges driven past (stored negated)
    for pos, kind, value in events:
        need = pos + value if kind == 0 else pos    # gate needs pos + reserve; station just needs pos
        while reach < need:                       # short of this gate: spend in hindsight
            if not banked:
                return -1
            reach += -heapq.heappop(banked)       # use the single biggest tank we passed
            stops += 1
        if kind == 1:
            heapq.heappush(banked, -value)          # bank this station's charge
    return stops

Complexity Analysis

Time: O((n + m) log n), where n is the number of stations and m the number of checkpoints. Sorting the n + m events dominates; each station is pushed onto the heap once and popped at most once, and each heap operation is O(log n).

Space: O(n) for the heap in the worst case (every station banked before a stop is taken).

For contrast, Solution 1 (the dynamic-programming approach) is O((n + m) · n) time and O(n) space: slower, but easier to prove and a perfectly respectable first answer. Landing it first and then improving to the heap-greedy is a strong way to show range under pressure.

Final Notes

1. "Decide in hindsight" is the unlock. The mental flip from "should I stop here?" to "drive on, and retroactively spend the biggest tank I have banked" is the core of the question. Say it out loud, it is the insight the interviewer is listening for.
2. Reserve checkpoints are gates, not extra distance. A reserve is a floor you must meet at a point, and the charge is not consumed there, so you cannot fold it into "a few more miles of road." Model each checkpoint as a gate demanding reach >= position + reserve, clear the gates in order, and the same greedy keeps working.
3. A max-heap is the natural home for "best option seen so far." Whenever the best choice is "the largest of everything I have passed and could still use," reach for a heap. Greedy-largest is provably optimal here: each stop adds the most range any single available stop could, so you can never need more stops than this method uses.
4. Handle the impossible case cleanly. If the heap empties before you clear a gate, return -1. A checkpoint can make a target that is otherwise easily reachable impossible (Example 3), so walk that case out loud, it is exactly the kind of input Amazon slips into the hidden tests.

It looks like a simple delivery problem, and it is really a greedy question. Find the greedy that works, then bend it around the reserve checkpoints instead of starting over. Keep the two moves handy, the "recharge in hindsight" heap and treating each checkpoint as a gate; that pair shows up in a lot of these problems. 🚀