Gas Station

Problem

A fleet of delivery vehicles runs a circular route through n fuel stations. Each station provides a fixed amount of fuel and requires a fixed amount to travel to the next station. A vehicle starts empty and can only travel if the tank stays non-negative throughout. Given gas[i] and cost[i] arrays, find a starting station that allows a full circuit, or return -1 if none exists.

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]  -> 3
 
gas  = [2, 3, 4]
cost = [3, 4, 3]        -> -1

Solution

Approach: single-pass greedy on the minimum prefix sum of net fuel.

Compute net[i] = gas[i] - cost[i] - the fuel you gain or lose crossing station i. Two facts make one pass enough. First, a circuit is possible at all only if sum(net) >= 0; if total gas is less than total cost the tank must run dry somewhere no matter where you start, so the code returns -1 when total < 0. Second, once a circuit is feasible, the best place to begin is the station right after the point where the running tank tank reaches its lowest value over the whole loop. At that minimum you have absorbed the worst cumulative deficit, so starting one step later means you face every remaining stretch with the largest possible head start, and the tank stays non-negative the rest of the way around.

The loop keeps tank (running net so far), total (full-circuit net), and min_tank. Every time tank dips to a new low it records start = i + 1. Trace gas=[1,2,3,4,5], cost=[3,4,5,1,2]: net is [-2,-2,-2,3,3], running tank -2,-4,-6,-3,0, minimum -6 at index 2, so start = 3 - the answer. The final start % len(gas) wraps the index when the minimum falls on the last station.

Edge cases: an exactly-balanced circuit (total == 0) still returns a valid start; a single infeasible station returns -1 via the total < 0 check; the modulo handles the minimum landing at the final index.

Complexity: O(n) time, O(1) space - one pass over the arrays tracking three scalars.