MediumArrayGreedyUpdated Sep 2026

134. Gas Station

Asked at Google, Meta, Amazon, Microsoft and 5 more

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

9

Problem

There are n gas stations on a circular road. At station i you can fill up gas[i] units of gas. Driving from station i to the next station costs cost[i] units of gas.

You start at one station with an empty tank. Your tank has no size limit, so you can hold as much gas as you like. You must drive around the circle once, always moving forward (station i → station i + 1, and the last station wraps back to station 0).

Return the index of the station where you should start so that you can finish the whole trip without ever running out of gas. If no start works, return -1. If a valid start exists, the problem guarantees it is unique.

A circular route with gas and cost

gas1234501234Station 3 gives 4 units — the winning startcost3451201234Leaving station 3 costs only 1 unit, so the tank grows
Each station gives gas[i] and each arrow to the next station costs cost[i]; you must pick a start that never lets the tank go negative.

Constraints

  • ●n == gas.length == cost.length
  • ●1 <= n <= 10^5
  • ●0 <= gas[i], cost[i] <= 10^4
  • ●The answer is unique when it exists

Examples

Example 1
Inputgas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output3
WhyStarting at station 3 you take 4 units. After paying 1 to reach station 4 you have 3, then add 5 to get 8. The tank never dips below zero, and you arrive back at station 3 with exactly 0 left. Starting anywhere else fails early — for example at station 0 you only get 1 unit but need 3 to move on.
Example 2
Inputgas = [2,3,4], cost = [3,4,3]
Output-1
WhyTotal gas is 9 and total cost is 10, so the trip is impossible no matter where you start. Even the best start (station 2) leaves you 1 unit short at the end.

Asked At

9 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
AmazonMediumView all Amazon questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
UberMediumView all Uber questions →
BloombergMediumView all Bloomberg questions →
Goldman SachsMediumView all Goldman Sachs questions →
TikTokMediumView all TikTok questions →

How to Think About It

1

First check: if total gas < total cost, it's impossible. Return -1. This is a necessary condition.

2

If total gas >= total cost, a solution is guaranteed to exist. The question is where to start.

3

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.

4

Algorithm: iterate with a running tank. If tank goes negative, reset start to i+1 and tank to 0.

5

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).

Greedy reset of the start

diff = gas - cost-2-2-23301234The first three stations each lose 2 units, so thetank dies therei=0: tank=-2 < 0 → start=1i=1: tank=-2 < 0 → start=2i=2: tank=-2 < 0 → start=3i=3: tank=3, i=4: tank=6 → start=3Every failure pushes the candidate start one stepforwardif sum(gas) < sum(cost): return -1tank += gas[i] - cost[i]if tank < 0: start = i + 1; tank = 0
Keep one running tank; whenever it goes negative, no station up to here can work, so restart from the next one.
ComplexityTime O(n)Space O(1)One pass over the arrays with a single running tank value; the total-gas check is also one pass and no extra storage is used.

What Trips People Up in Real Interviews

1

Not checking the total gas vs total cost first. If total gas < total cost, no solution exists — return -1 immediately.

2

Trying all starting positions. That's O(n²). The greedy approach is O(n).

3

Forgetting that the route is circular. After the last station, you return to the first.

4

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.

5

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

O(n) time
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 start

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Gas Station?

Gas Station is asked at Google, Meta, Amazon, Microsoft, Apple, Uber, Bloomberg, Goldman Sachs, TikTok. 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.