Skip to main content
DSA patterns

Gas Station

mediumGreedy Must-doAmazonUberSwiggy

Problem statement

There are n gas stations arranged in a circle. Station i has gas[i] units of fuel available, and it costs cost[i] units of fuel to drive from station i to the next one going clockwise.

You start with an empty tank at one station of your choosing. Find a starting station from which you can make it all the way around the circle back to where you started, or return -1 if no such station exists. If a valid starting station exists, it's guaranteed to be the only one.

Examples

Example 1

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

Output: 3

Explanation: Starting at station 3, the tank never goes negative on the way around: fill up 4, spend 1 to reach station 4 (net +4), fill up 5, spend 2 to reach station 0 (net +7), fill up 1, spend 3 to reach station 1 (net +6), fill up 2, spend 4 to reach station 2 (net +5), fill up 3, spend 5 to get back to station 3 (net +3, exactly enough).

Example 2

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

Output: -1

Explanation: The total gas available (2+3+4=9) is less than the total cost of driving the whole circle (3+4+3=10), so no starting station can possibly make it all the way around.

Hints

Hint 1: Before searching for a starting point at all, compare the total gas available across every station to the total cost of the whole circuit — if the total cost is higher, no starting point can work, no matter where you begin.

Approach

Optimal: One-pass greedy

Intuition

The second pass in the "better" approach only exists to check one fact: does the total gas across the whole circuit cover the total cost? That's a single sum comparison you can compute in the very same pass that finds the candidate starting station — there's no need to walk the circle a second time just to confirm it. Track the running total (never reset) alongside the running tank (reset on failure); at the end, the total tells you directly whether a solution exists at all.

Steps

  1. Set total = 0, tank = 0, and start = 0.
  2. Walk i from 0 to n-1: compute diff = gas[i] - cost[i], and add it to both total and tank.
  3. If tank goes negative, this candidate has failed — set start = i + 1 and reset tank to 0 (but total keeps accumulating, uninterrupted).
  4. Once the loop finishes, total tells you everything: if it's negative, no station works, so return -1.
  5. Otherwise, start is guaranteed to be the one valid starting station — return it directly, no second pass required.

Dry run

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

i diff total tank tank < 0? start after
0 -2 -2 -2 yes 1
1 -2 -4 -2 yes 2
2 -2 -6 -2 yes 3
3 +3 -3 3 no 3
4 +3 0 6 no 3

total ends at 0 (≥ 0), so the answer is start = 3 — no second pass needed to confirm it.

Edge cases: gas = [2, 3, 4], cost = [3, 4, 3] gives total = -1 at the end, so the function returns -1 directly, even though a "candidate" start value was tracked along the way.

Complexity

Time O(n) - a single pass over the stations; no second pass is needed.

Space O(1) - a running tank, a running total, and a candidate index.

class Solution:
    def canCompleteCircuit(self, gas, cost):
        n = len(gas)
        total = 0
        tank = 0
        start = 0
        for i in range(n):
            diff = gas[i] - cost[i]
            total += diff
            tank += diff
            if tank < 0:
                start = i + 1
                tank = 0
        return start if total >= 0 else -1


if __name__ == "__main__":
    print(Solution().canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))
    print(Solution().canCompleteCircuit([2, 3, 4], [3, 4, 3]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: "find a starting point on a circular route where a running balance never goes negative"
  • Idea: reset your candidate start to the very next station the moment the running tank goes negative; the total gas vs. total cost comparison alone tells you if any solution exists
  • Cost: O(n) time, O(1) space (one-pass greedy); still O(n) time with a two-pass verify step; O(n^2) for the brute-force simulate-every-start approach
  • Trap: forgetting the feasibility check (total gas < total cost) and returning a "candidate" start that doesn't actually work

Interview follow-ups

  • What if the car had a limited tank capacity instead of an unlimited one?

    The single running-tank trick stops being enough, because now excess fuel can be wasted rather than carried forward indefinitely. Simulating with a capped tank generally needs trying each candidate starting point directly (or a more careful greedy that also tracks when the tank would overflow), which pushes the approach back toward O(n^2) unless the specific cap values allow a further trick.

  • The gas and cost values arrive as a live stream (stations reporting in real time) rather than a fixed array you can read twice.

    The one-pass optimal approach already works well here, since it never needs a second read — track total and tank exactly as before as each station reports in, and reset the candidate start whenever tank goes negative. Once the stream ends, the same total >= 0 check gives the answer with no need to have buffered the whole stream.

Frequently asked questions

If starting from station s fails because the tank goes negative at station i, then any station between s and i would arrive at station i with the same or less fuel than starting at s did — they lose whatever surplus s had already banked by the time they'd reach i. So none of them could possibly succeed either, and it's safe to jump the candidate straight to i + 1 without checking them individually.

The circuit is a fixed loop, so the total fuel gained and the total fuel spent don't depend on where you start — only the order you encounter the ups and downs changes. If the total gas is less than the total cost, no ordering can make the sum work out, so it's impossible everywhere. If the total gas is at least the total cost, it's a mathematical guarantee (not just a heuristic) that some starting point makes the running tank stay non-negative the whole way around.

It mirrors a real capacity-planning question: given a rotation of maintenance windows or batch jobs, each producing or consuming some budget (CPU credits, a rate-limit allowance, a deploy budget), is there a starting point in the cycle from which the running balance never goes negative? The greedy "reset on going negative" technique is the same one used to find such a safe starting point in scheduling problems.

The problem guarantees a unique answer if one exists, so yes for this problem specifically — but the same greedy technique, run without that guarantee, would only be certain to find a valid starting point, since it never explicitly rules out the possibility of multiple valid ones existing elsewhere in the circuit.