#134 Gas Station
frequently reported atFlipkartInfosysBloombergAmazonMicrosoftGoogle
the problem
In plain words
n stations sit on a circular road. Station i gives gas[i] fuel, and driving from station i to the next one costs cost[i]. Starting with an empty tank, return the start index that lets you drive the full circle once, or −1. If an answer exists, it is unique.
in gas = [1,2,3,4,5], cost = [3,4,5,1,2]
out 3
in gas = [2,3,4], cost = [3,4,3]
out -1
- 1 ≤ n ≤ 10⁵
- 0 ≤ gas[i], cost[i] ≤ 10⁴
- The answer, if any, is unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy choice
If total gas ≥ total cost, a start exists. If the tank goes negative at i, nobody from the current start through i can be the start, so jump straight to i + 1.
solutions
From brute force to optimal
For each start, drive around and check that the tank never goes negative.
- For each start s, walk n stations with a running tank.
- Break on a negative tank; return s if all n steps succeed.
n starts × up to n steps each.
A couple of counters.
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int n = gas.length; for (int start = 0; start < n; start++) { int tank = 0, steps = 0; while (steps < n) { int i = (start + steps) % n; tank += gas[i] - cost[i]; if (tank < 0) break; // ran dry before the next station steps++; } if (steps == n) return start; // made the full loop } return -1; }}Keep total (the whole loop) and tank (since the current start). Reset the start when the tank goes negative.
- total = tank = start = 0.
- Add gain = gas[i] − cost[i] to both.
- If tank < 0: start = i + 1, tank = 0.
- Return total ≥ 0 ? start : −1.
One pass.
Three integers.
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < gas.length; i++) { int gain = gas[i] - cost[i]; total += gain; tank += gain; if (tank < 0) { start = i + 1; // no station in [start..i] can work tank = 0; } } return total >= 0 ? start : -1; }}Dry run
in the room
How to say it in the interview
talk track
- State both facts: (1) total ≥ 0 ⇔ an answer exists; (2) a failure at i rules out every start in [start..i].
- Prove (2): any start between them arrives at each station with no more fuel than the original start had.
traps
- Returning
startwithout checkingtotal. - Simulating the wrap-around. It isn't needed, because
totalcovers it.
what they ask next
Follow-ups
Why is the found start correct and not just the last candidate?
The suffix from start never goes negative. Total ≥ 0 means the prefix before start has a deficit no bigger than that suffix's surplus, so the wrap-around succeeds too.
before you submit
Edge cases to test
- One station: the answer is 0 if gas[0] ≥ cost[0], else −1.
- Total gas exactly equals total cost → a start still exists (the tank ends at 0).
- The answer is the last station: every earlier start drives almost all the way before failing, which makes the O(n²) simulation crawl.
practise next
Similar problems
- #53Maximum SubarrayMediumin Arrays & Strings
- #55Jump GameMediumin Greedy