Gas Station Solution

Problem

There are N gas stations arranged in a circle. At each station you can collect some fuel, and travelling to the next station burns a fixed amount. Starting with an empty tank, find the index of the station from which you can complete the full loop — or return -1 if no valid starting point exists.

Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Output: 3
Explanation: Starting at station 3, you collect enough fuel at each stop to complete the full loop without your tank ever going negative.

Counter-example: gas = [2, 3, 4], cost = [3, 4, 3] → -1. The total fuel (9) equals total cost (10), so the circuit is physically impossible regardless of starting point.

Intuition

At each station, your tank gains or loses gas[i] - cost[i] net fuel. If the sum of all net values is negative, the trip is impossible — there simply isn't enough total fuel. Otherwise, a valid starting point is guaranteed to exist and is unique. The key greedy insight: the moment your running tank goes negative, every station you've passed since the last reset is already disqualified as a starting point (they all begin with less accumulated fuel than you had), so the next candidate must be the very next station.

Approach 1 — Brute Force

For each station as a candidate start, simulate the full circuit and check whether the tank ever goes negative.

For each station start from 0 to n-1, initialize tank = 0
Simulate n steps starting from start, wrapping around with modulo
At each step add gas[station] - cost[station] to the tank
If the tank ever drops below zero, this start fails — break and try the next
If all n steps complete without the tank going negative, return start
If no start works, return -1

1def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
2    n = len(gas)
3    for start in range(n):
4        tank = 0
5        valid = True
6        for step in range(n):
7            station = (start + step) % n
8            tank += gas[station] - cost[station]
9            if tank < 0:
10                valid = False
11                break
12        if valid:
13            return start
14    return -1

Time: O(n²) — each of n candidate starts may require simulating up to n steps.
Space: O(1) — only a running tank and loop indices.

Approach 2 — Greedy Single Pass

If your running tank goes negative at station i, every station from the current start through i is eliminated as a candidate — they all began with less accumulated fuel than you had, so they'd fail even sooner at station i. Reset the candidate start to i + 1 and keep a separate total_surplus to detect the overall impossible case.

Initialize total_surplus = 0, current_surplus = 0, start = 0
For each station i, compute net = gas[i] - cost[i] and add to both variables
If current_surplus < 0, set start = i + 1 and reset current_surplus = 0
After the full pass, if total_surplus < 0 the circuit is impossible — return -1
Otherwise return start (guaranteed to be the unique valid answer)

1def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
2    total_surplus = 0
3    current_surplus = 0
4    start = 0
5
6    for i in range(len(gas)):
7        net = gas[i] - cost[i]
8        total_surplus += net
9        current_surplus += net
10
11        if current_surplus < 0:
12            # Every station from previous start through i is disqualified
13            start = i + 1
14            current_surplus = 0
15
16    return start if total_surplus >= 0 else -1

Time: O(n) — a single linear pass with no inner loop.
Space: O(1) — three scalar variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Debugging or verifying correctness on tiny inputs
Greedy Single Pass	O(n)	O(1)	Always — same constant space with linear time

Common Mistakes

Filtering starts by gas[i] >= cost[i] — a station doesn't need to cover its own cost; surplus fuel accumulated from previous stops can make it viable even with a local deficit.
Setting start = i instead of start = i + 1 when current_surplus goes negative — the station where you ran out is itself invalid; the new candidate is the very next one.
Returning start unconditionally without checking total_surplus >= 0 — if total fuel is less than total cost, the greedy still sets a start value but the circuit is impossible.
Running a second verification pass after the greedy selects a candidate — the greedy guarantee is mathematical: if total_surplus >= 0, the returned start is provably correct.
Applying % n modulo inside the greedy loop — the greedy's single forward pass handles the circular structure implicitly through total_surplus; modulo arithmetic is only needed in the brute force.

Gas Station — Solution