How do you approach Gas Station?

If total gas < total cost, it's impossible to complete the circuit.

What is the time complexity of Gas Station?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on Gas Station?

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem. Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic. Missing the case where two greedy choices tie and the tiebreak decides correctness.

gitGood.dev

← Back to problems

Gas Station

MediumAlgorithms

Description

There are `n` gas stations along a circular route, where the amount of gas at the `i`th station is `gas[i]`. You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `i`th 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**.

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

Output: 3

Explanation: Start at station 3 (index 3). Tank = 0 + 4 = 4. Travel to station 4: Tank = 4 - 1 + 5 = 8. Travel to station 0: Tank = 8 - 2 + 1 = 7. Travel to station 1: Tank = 7 - 3 + 2 = 6. Travel to station 2: Tank = 6 - 4 + 3 = 5. Travel to station 3: Tank = 5 - 5 = 0.

Example 2

Input: gas = [2,3,4], cost = [3,4,3]

Output: -1

Explanation: Total gas = 9, total cost = 10. Not enough gas to complete the circuit.

Constraints

- n == gas.length == cost.length - 1 <= n <= 10^5 - 0 <= gas[i], cost[i] <= 10^4

Gas Station: approach, complexity and pitfalls

A medium greedy problem, graded against 7 test cases (4 of them hidden).

The pattern: Greedy

Take the locally best option each step and prove it stays globally optimal.

Reach for it when you see: Interval scheduling, jump/reachability questions, or an optimisation with an obvious local choice.

More Greedyproblems →

If you are stuck

Show the 3-step hint ladder

If total gas < total cost, it's impossible to complete the circuit.
If the tank goes negative at some point, the starting station must be after that point.
Use a greedy approach: track current tank and reset the start whenever tank goes negative.

The optimal approach

Show the approach: Greedy

If total gas >= total cost, a solution exists. Track the current tank - if it goes negative, reset the starting station to the next position. The key insight is that if starting from station A fails at station B, then no station between A and B can be the answer.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Greedy mistakes

These apply to the pattern as a whole, not just this problem.

Assuming the locally best choice is globally best with no exchange argument. If you cannot state why it holds, it is probably a DP problem.
Sorting by the wrong key - by start time where the proof needs end time is the interval-scheduling classic.
Missing the case where two greedy choices tie and the tiebreak decides correctness.