Domain 2MediumCORE

Gas Station

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Greedy

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:

  • n≥1n \ge 1 (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 ii, simulate the journey from there to ensure the tank never drops below zero before returning to start. If successful, return ii. Why this fails: This simulation takes O(n)O(n) for each of the nn starts, resulting in O(n2)O(n^2) time complexity. With n=104n=10^4, that’s roughly 10810^8 operations, which risks Time Limit Exceeded (TLE).

We need a linear solution (O(n)O(n)). 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:

  1. Initialize total_tank (cumulative net gas across entire route) and current_tank (net balance for current potential path). Both start at 0.
  2. Iterate through each station, calculating the net gain (gas[i] - cost[i]). Add this to both accumulators.
  3. 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).
  4. Inside the loop: if current_tank drops below zero, it means no station between our current candidate and index ii could be a valid starting point (due to transitivity). Reset start = i + 1 and reset current_tank = 0.
  5. After iterating through all stations, check the final condition: if total_tank >= 0, return start; otherwise -1.

Complexity Analysis

  • Time: O(n)O(n) - We traverse the arrays exactly once.
  • Space: O(1)O(1) - 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_tank is negative after the loop, we correctly return -1. This covers cases where no solution exists regardless of starting point.
  • Single Station (n=1n=1): 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_index updates to 1 correctly for the next iteration or final check.