134. Gas Station
Model: qwen3.5:9b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 41.5%
Problem Breakdown
We are given a circular route with n gas stations. Each station provides a specific amount of fuel (gas[i]) and requires a certain cost to travel to the next station (cost[i]). We start at an empty tank at one chosen index, fill up there, move clockwise, refill at each stop (implicitly), paying the travel cost along the way.
Inputs: Two integer arrays gas and cost, both of length n.
Output: The starting station’s index if a complete circuit is possible; otherwise -1.
Constraints & Edge Cases:
- (no empty input).
- Values are non-negative.
- If a solution exists, it is guaranteed to be unique.
- Overflow: While sums can exceed standard integer limits in other languages, Python handles arbitrary precision integers automatically, so we don’t need explicit overflow checks for the logic itself.
Intuition
A naive approach would be brute force: iterate through every possible starting station , simulate the journey from there to ensure the tank never drops below zero before returning to start. If successful, return . Why this fails: This simulation takes for each of the starts, resulting in time complexity. With , that’s roughly operations, which risks Time Limit Exceeded (TLE).
We need a linear solution (). The key insight relies on analyzing the net gain at each station: diff[i] = gas[i] - cost[i].
If we start from index 0 and our tank balance drops below zero at some point, it means that starting segment (from current start to failure point) is impossible. Crucially, any intermediate station within that failed segment cannot be a valid starting point either. Why? Because if the cumulative sum dropped below zero relative to start, adding more fuel from an earlier invalid stop wouldn’t compensate for the deficit accumulated before it. Therefore, we can safely skip all stations up to and including the failure point and try starting at the next station (i + 1).
Approach
We use a single pass greedy algorithm:
- Initialize
total_tank(cumulative net gas across entire route) andcurrent_tank(net balance for current potential path). Both start at 0. - Iterate through each station, calculating the net gain (
gas[i] - cost[i]). Add this to both accumulators. - If
total_tank < 0, we can immediately return-1. We don’t have enough gas overall to complete the circuit regardless of where we start. (Note: In implementation, checking at the end is sufficient and avoids premature exits if prefix sums dip temporarily). - Inside the loop: if
current_tankdrops below zero, it means no station between our current candidate and index could be a valid starting point (due to transitivity). Resetstart = i + 1and resetcurrent_tank = 0. - After iterating through all stations, check the final condition: if
total_tank >= 0, returnstart; otherwise-1.
Complexity Analysis
- Time: - We traverse the arrays exactly once.
- Space: - Only a constant amount of extra variables (
current_tank,total_tank,start) are used regardless of input size.
Solution
def canCompleteCircuit(gas, cost):
total_tank = 0 # Tracks if the circuit is possible overall
current_tank = 0 # Tracks balance for the specific starting candidate
start_index = 0 # The potential starting station
n = len(gas)
for i in range(n):
net_gain = gas[i] - cost[i]
total_tank += net_gain
# If current path fails, reset.
# Any index between start and i is invalid because we couldn't reach i+1 from them either.
if current_tank < 0:
start_index = i + 1
current_tank = 0
return -1 if total_tank < 0 else start_index
Edge Cases Handled
- Total Gas Insufficient: If
total_tankis negative after the loop, we correctly return-1. This covers cases where no solution exists regardless of starting point. - Single Station (): The logic holds; if
gas[0] >= cost[0], it returns 0, else -1. - Failure at First Index: If index 0 fails immediately (
current_tank < 0),start_indexupdates to 1 correctly for the next iteration or final check.