LeetEye LeetEye
Medium Greedy ~5 min

Gas Station

greedy gas-station

Problem

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Examples

Example 1
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Start at station 3, tank = 4. Travel to station 4, tank = 4-1+5 = 8. Continue around.
Example 2
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Key Insight

If total gas >= total cost, solution exists. If you can't reach station j from station i, start from j+1.

If total_gas >= total_cost, solution exists. Greedily start from next station whenever tank goes negative. The last valid start is the answer.

How to Approach This Problem

Pattern Recognition: When you see keywords like gas station greedy, think Greedy.

Step-by-Step Reasoning

1 A solution exists if:
Answer: total_gas >= total_cost
If total gas can cover total cost, you can complete the circuit from some starting point.
2 At station i, the net effect is:
Answer: gas[i] - cost[i]
You gain gas[i] but spend cost[i] to reach next station.
3 If starting from station i, you can't reach station j (tank < 0):
Answer: No station from i to j-1 can be the start
If you can't reach j from i with accumulated gas, you can't reach j from any station between i and j (you'd have less gas).
4 When tank goes negative at station j:
Answer: Start = j + 1, reset tank
j and all stations before it in current attempt can't be the start. Try j+1.
5 One pass is sufficient because:
Answer: All of above
Total check ensures solution. Greedy elimination finds it.

Solution

def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
    # Check if solution exists
    if sum(gas) < sum(cost):
        return -1
    
    start = 0
    tank = 0
    
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        
        if tank < 0:  # Can't reach next station
            start = i + 1  # Try starting from next
            tank = 0
    
    return start

Complexity Analysis

Time O(n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Greedy problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye