Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Gas Station
• Topics: Array, Greedy

Problem gist

There are n gas stations arranged in a circle. Station i provides gas[i] units of fuel, and driving from station i to the next station costs cost[i] units. The car starts with an empty tank. The task is to return an index from which the car can complete one full clockwise circuit, or -1 if no such index exists.

A direct solution can try every starting station and simulate a full trip. That takes up to $O(n^2)$ time because the same stretches of road are checked repeatedly. The optimal solution avoids those repeated simulations by using two observations about fuel balance.

Deriving the greedy solution

For each station, define its net fuel as:

net[i] = gas[i] - cost[i]

First consider the entire circle. If the sum of all net values is negative, the route requires more fuel than all stations provide. No starting point can fix that, so the answer must be -1.

If the total is nonnegative, at least one start works. The remaining question is how to find it.

Scan from left to right while tracking the fuel accumulated from a candidate starting station. Suppose the candidate is start, and the running balance becomes negative after paying the cost at station i. Starting at start clearly fails before reaching i + 1. More importantly, every station between start and i also fails.

Why can they all be skipped? Before reaching any intermediate station j, the trip from start still had a nonnegative balance; otherwise the algorithm would already have reset. Removing that nonnegative prefix cannot turn the negative balance through i into a nonnegative one. Therefore a trip beginning at j also runs out of fuel by station i.

The next possible candidate is consequently i + 1. Reset the running balance to zero and continue. Each station is processed once. At the end, the final candidate is valid exactly when the total balance is nonnegative.

This separates two responsibilities cleanly:

• total_balance decides whether any complete circuit is possible.
• current_balance identifies and discards ranges that cannot contain a valid start.

The algorithm runs in $O(n)$ time and uses $O(1)$ auxiliary space.

Python solution

from collections.abc import Sequence


class Solution:
    def canCompleteCircuit(self, gas: list[int], cost: list[int]) -> int:
        """Return a station that can complete the circuit, or -1 if none can."""
        self._validate_inputs(gas, cost)
        if not gas:
            return -1

        candidate_start = 0
        current_balance = 0
        total_balance = 0

        for station_index, (fuel_available, travel_cost) in enumerate(
            zip(gas, cost)
        ):
            net_fuel = fuel_available - travel_cost
            current_balance += net_fuel
            total_balance += net_fuel

            if current_balance < 0:
                # No station from candidate_start through station_index can
                # reach station_index + 1, so skip that entire range.
                candidate_start = station_index + 1
                current_balance = 0

        return candidate_start if total_balance >= 0 else -1

    @staticmethod
    def _validate_inputs(gas: Sequence[int], cost: Sequence[int]) -> None:
        """Reject malformed station data while accepting LeetCode's inputs."""
        if len(gas) != len(cost):
            raise ValueError("gas and cost must contain the same number of stations")

        if any(amount < 0 for amount in gas):
            raise ValueError("gas amounts must be nonnegative")

        if any(amount < 0 for amount in cost):
            raise ValueError("travel costs must be nonnegative")

Interview follow-ups

Why does a nonnegative total guarantee that the final candidate works?

Every reset happens only after a scanned segment has a negative sum. The algorithm discards that entire segment and starts immediately after it. When the total sum is nonnegative, the fuel contributed by the stations outside all discarded negative segments is sufficient to offset those deficits after the route wraps around.

Equivalently, imagine prefix sums of net fuel and choose the position immediately after their minimum value. Every later prefix relative to that minimum is nonnegative, and after wrapping, the nonnegative total keeps the remaining relative prefixes nonnegative as well. The greedy resets find that same kind of position without storing the prefix-sum array.

How would the solution return every valid starting station?

The single-candidate greedy algorithm deliberately discards information and is not enough when multiple answers must be reported. Use prefix sums over two copies of the net-fuel array. A start s is valid when the minimum prefix sum over the next n steps is at least the prefix sum at s.

A monotonic deque can maintain that minimum as the length-n window moves from one start to the next. This checks all starts in $O(n)$ time with $O(n)$ space. Simulating the circuit from every start is simpler but costs $O(n^2)$ time.

What changes if the fuel tank has a fixed capacity?

The original proof no longer applies. With unlimited capacity, extra fuel can always be carried forward; with a capacity limit, fuel may be discarded at a station because the tank is already full. Removing an earlier part of a route can therefore change how much fuel is lost to overflow, so a failed segment can no longer be eliminated by the same greedy argument.

The straightforward approach is to simulate each starting station while updating the tank as min(capacity, tank + gas[i]) - cost[i]. It uses $O(1)$ extra space and $O(n^2)$ time in the worst case. Improving that bound requires a more specialized range-composition data structure that tracks how a segment transforms an incoming fuel level; the simple total-sum test is insufficient.

How would the solution also report the tank level after each leg?

First find a valid start with the greedy pass. If one exists, make a second pass of exactly n stations beginning at that index. Add the station’s gas, subtract the outgoing travel cost, and append the remaining tank level after each leg.

The second pass is also linear, so the total time remains $O(n)$. The output itself contains n values and therefore requires $O(n)$ space. Keeping this simulation separate from candidate selection makes the core correctness argument unchanged.

Can the input arrays be processed as a one-pass stream?

Yes, if only the starting index is needed and the stream provides paired gas and cost values in order. The algorithm stores only the current index, candidate start, current balance, and total balance. It does not need to revisit earlier stations because a negative current balance permanently eliminates the scanned candidate range.

This preserves $O(n)$ time and reduces working memory to $O(1)$ beyond the stream itself. The result cannot be finalized until the stream ends, because a negative overall total must still produce -1 even if a promising candidate was found earlier.