Difficulty: MediumGreedy

Gas Station

Problem in Plain English

There are n gas stations in a circle, each giving some gas and charging some cost to reach the next one. Find the station to start from so the car completes the full loop, or report that it is impossible.

Problem Statement

There are n gas stations on a circular route. Station i provides gas[i] fuel; traveling clockwise to the next station costs cost[i]. After station n - 1, the next station is 0. Start with an empty, unlimited-capacity tank, collect fuel at each visited station, and pay for its outgoing leg.

Return the zero-based starting index that completes exactly one circuit without running out of fuel, or -1 if no start works. A valid starting index is guaranteed unique when a solution exists.

Constraints

n equals the length of both input arrays.
$1 \le n \le 10^5$ .
$0 \le \text{gas}[i], \text{cost}[i] \le 10^4$ .
If a valid starting index exists, it is unique.

Examples

Example 1

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

Starting at 3, the tank after each outgoing leg is 3, 6, 4, 2, 0 along the station order 3, 4, 0, 1, 2. All five legs are affordable, including the last leg back to 3. Starts 0, 1, and 2 fail immediately; start 4 reaches a negative tank at station 2.

Example 2

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

The route has 9 units of fuel but costs 10 units. Starting at 2 initially builds a tank of 1, then reaches 0 at station 0 and -1 at station 1. No change of starting point can supply the missing unit.

Example 3

Input: gas = [0], cost = [0]
Output: 0

The single outgoing leg returns to the same station and costs no fuel. A tank of zero is sufficient; failure requires a negative balance, not merely an empty tank.

Example 4

Input: gas = [0,2,0], cost = [1,0,1]
Output: 1

Only station 1 works: its tank progresses 2, 1, 0 through station order 1, 2, 0. Station 2 has no fuel for its first leg. Equal total fuel and cost are feasible even with zero-fuel stations and an empty tank on arrival.

Intuition

Think of each station as a net fuel change: the fuel collected minus the cost of its outgoing leg. The tank must stay nonnegative after every leg, so having enough fuel overall is necessary but does not make every start valid. In Example 1 the changes are -2, -2, -2, +3, +3: station 3 accumulates fuel before crossing the three deficits. If a candidate first fails at station i, all starts between that candidate and i also fail there or earlier, because they lose the nonnegative fuel accumulated before reaching them. This lets one reset eliminate a whole block of candidates.

Approaches

Try Every Start

Solution Details

Reveal Try Every Start: intuition, complexity, and code

Intuition

Try each station with a fresh empty tank and simulate one clockwise circuit. This directly tests the requirement, but repeated trials revisit the same legs. In Example 1 starts 0, 1, and 2 fail on their first leg; start 3 survives all five legs.

Step-by-Step Logic

For each possible start, reset tank to zero and assume this trial succeeds. In Example 1 first try station 0.
For each of the n legs, select station (start + step) % n so that the index wraps at the end. Add its fuel and subtract its outgoing cost before checking affordability.
If the balance becomes negative, stop this trial and try the next start. Example 1 starts 0, 1, and 2 each produce -2 on their first leg.
If all n legs finish with a nonnegative balance, return that start. From 3, the balances are 3, 6, 4, 2, 0, so return 3.
If every start fails, return -1; every possible starting station has then been tested.

Why It Works

After each simulated leg, tank equals all fuel collected so far minus all fuel spent from this trial's starting point. Since fuel is collected before paying for a leg, a negative resulting balance means that leg cannot be completed; any nonnegative balance is affordable. A trial succeeds only after exactly n affordable legs, which visit every station once and return to its start. The outer loop checks every possible start unless it finds such a circuit, so returning -1 rules out all candidates. The uniqueness guarantee makes the first successful index the requested answer.

Dry Run

Try Every Start: variable states at each step
start	step	station to next	fuel change	tank before to after	decision
0	0	0 to 1	-2	0 to -2	fail; next start
1	0	1 to 2	-2	0 to -2	fail; next start
2	0	2 to 3	-2	0 to -2	fail; next start
3	0	3 to 4	+3	0 to 3	continue
3	1	4 to 0	+3	3 to 6	wrap
3	2	0 to 1	-2	6 to 4	continue
3	3	1 to 2	-2	4 to 2	continue
3	4	2 to 3	-2	2 to 0	all 5 legs done; return 3

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

There are at most n trials with at most n legs each. A route with a single deficit at the last station and zero changes elsewhere forces n + (n - 1) + ... + 1 legs before returning -1, proving quadratic worst-case time. Only scalar counters, a tank balance and a flag are allocated; the input arrays are read without copies or mutation. The returned index uses constant space.

Code

Solution.java

1class Solution {2    public int canCompleteCircuit(int[] gas, int[] cost) {3        int n = gas.length;4        for (int start = 0; start < n; start++) {5            int tank = 0;6            boolean ok = true;7            for (int step = 0; step < n; step++) {8                // Modulo wraps each trial without allocating a doubled route.9                int station = (start + step) % n;10                tank += gas[station] - cost[station];11                // Zero fuel is legal; a negative balance makes this leg unaffordable.12                if (tank < 0) {13                    ok = false;14                    break;15                }16            }17            if (ok) {18                return start;19            }20        }21        return -1;22    }23}

Hints

Hint 1

Compare the total gas available with the total cost of the loop before testing any start.

Hint 2

Ask what a failed trip from one station to another says about every station in between.

Hint 3

Track one running tank and restart the candidate just past each failure point.

Edge Cases

A single station returns 0 when its fuel covers its self-loop cost, including both values zero; otherwise it returns -1.
A negative total net change makes every start impossible, even if one station offers a large temporary surplus.
A tank reaching zero after a leg is valid. Example 4 finishes with exactly zero after wrapping.
A valid start may be the last station: several failures can move the candidate there before a large final surplus pays for the prefix.
For n equal to 100000, total fuel or cost can reach one billion; do not choose an accumulator narrower than Java int.

Common Mistakes and Interview Tips

Resetting when the tank is zero rejects affordable legs and can move the candidate beyond the array on a valid all-zero single-station route.
Restarting at the failure station reuses a disproved start; move to the station immediately after it.
Returning the surviving candidate without checking the total can report a suffix that succeeds while the wrapped circuit fails.
Choosing the largest fuel station or largest individual surplus ignores the order of deficits and does not prove circuit feasibility.
Forgetting modulo in direct simulation skips the wrapped prefix or accesses outside the array.
Treating the final greedy tank as a full-loop tank: it contains only the candidate suffix; the total guard and minimum-prefix invariant justify wraparound.

Key Takeaway

When a first failure eliminates every candidate in a segment, discard that segment as a unit. For a circular resource balance, a global minimum prefix gives a safe starting boundary, and the total balance decides whether wraparound is affordable.