FAANGPrep Sprint
Gas Station
Find the starting gas station to complete the circuit.
Examples
Stations 0, 1 and 2 each run dry at once; from station 3 the tank never drops below 0 on the full lap.
The route offers 9 gas but burns 10, so no start can finish.
Two stretches run dry, and the lap from the last station wraps past the end.
Problem Understanding
There are n gas stations on a circular route. Station i gives gas[i] units of gas, and driving from station i to the next one (from the last station back to station 0) burns cost[i].
The car starts with an empty tank at a station of your choosing. Return the index of that station if the car can drive round the whole circuit once, otherwise return -1. If a solution exists, it is guaranteed to be unique.
Strategy
One pass, adding each station’s net = gas[i] - cost[i] to two sums:
total_tank, the whole trip. If it ends below 0, the route burns more than it offers and no start can finish: return -1.curr_tank, the tank since the candidatestart. If it drops below 0 at stationi, no station fromstarttoican be the start, so setstart = i + 1and empty the tank.
If total_tank ends at 0 or more, start is the answer.
Interactive Visualization
CLOCKWISE FROM THE TOP · +GAS ABOVE EACH STATION · −COST ON EACH LEG · OUTLINED = CANDIDATE START
EMPTY TANKS, START AT 0
start
0
tank since start
0
whole trip
0
Answer
—
the rule
whole trip ≥ 0 → start, else −1
Both tanks start empty, and station 0 is the first candidate start
Next
Station 0: fill up with 1, then the leg to station 1 burns 3
gas/cost
The route drawn as the loop it is. Above each station is the gas it gives; on each arrow, what that leg burns. The candidate start is outlined and the legs driven since it are lit. When the tank runs dry the failing leg turns red and the stretch is greyed out — none of those stations can be the start.
Try Late start: two stretches run dry, the answer is the last station, and the lap it completes wraps past the end.