Gas Station
Asked at Google, Meta, Amazon, Microsoft, Apple, Uber
Problem
There are n gas stations along a circular route. You have two arrays: gas[i] is the amount of gas at station i, and cost[i] is the cost to travel to the next station. Return the starting gas station index if you can travel around the circuit once, otherwise return -1.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Uber | Medium | View all Uber questions → |
How to Think About It
First check: if total gas < total cost, it's impossible. Return -1. This is a necessary condition.
If total gas >= total cost, a solution is guaranteed to exist. The question is where to start.
Greedy insight: if you run out of gas between start and station j, no station between start and j can be the answer. They all have less gas available than start.
Algorithm: iterate with a running tank. If tank goes negative, reset start to i+1 and tank to 0.
Visual walkthrough for gas=[1,2,3,4,5], cost=[3,4,5,1,2]:
total gas=15, total cost=15 → possible.
i=0: tank=1-3=-2 → reset. start=1, tank=0.
i=1: tank=2-4=-2 → reset. start=2, tank=0.
i=2: tank=3-5=-2 → reset. start=3, tank=0.
i=3: tank=4-1=3. tank=3+5-2=6.
Result: start=3.
Edge cases: one station, all stations have enough gas, circular route where start is the last station.
Optimal Approach
Step 1: If sum(gas) < sum(cost), return -1.
Step 2: Initialize tank = 0, start = 0.
Step 3: For i from 0 to n-1:
tank += gas[i] - cost[i]
If tank < 0:
start = i + 1
tank = 0
Step 4: Return start.
Time: O(n). Space: O(1).
What Trips People Up in Real Interviews
Not checking the total gas vs total cost first. If total gas < total cost, no solution exists — return -1 immediately.
Trying all starting positions. That's O(n²). The greedy approach is O(n).
Forgetting that the route is circular. After the last station, you return to the first.
Not resetting the tank and start when tank goes negative. If you run out of gas, no station between start and the current position can be the answer.
Resetting the tank to gas[i] - cost[i] instead of 0 when tank goes negative. The tank should reset to 0 and start moves to i + 1. Setting it to a non-zero value might keep a negative tank, breaking the greedy invariant.
Solution Code
def canCompleteCircuit(gas, cost):
if sum(gas) < sum(cost):
return -1
tank = 0
start = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return startFrequently Asked Questions
What is the Gas Station problem?
There are n gas stations along a circular route. You have two arrays: `gas[i]` is the amount of gas at station i, and `cost[i]` is the cost to travel to the next station. Return the starting gas station index if you can travel around the circuit once, otherwise return -1.
How do you solve Gas Station?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Gas Station?
Gas Station is asked at Google, Meta, Amazon, Microsoft, Apple, Uber. It is a medium difficulty problem.
What are common mistakes on Gas Station?
- Not checking the total gas vs total cost first. If total gas < total cost, no solution exists — return -1 immediately.
- Trying all starting positions. That's `O(n²)`. The greedy approach is `O(n)`.
- Forgetting that the route is circular. After the last station, you return to the first.
- Not resetting the tank and start when tank goes negative. If you run out of gas, no station between start and the current position can be the answer.
- Resetting the tank to `gas[i]` - `cost[i]` instead of 0 when tank goes negative. The tank should reset to 0 and start moves to i + 1. Setting it to a non-zero value might keep a negative tank, breaking the greedy invariant.