125.Gas Station

MediumGreedy · 4/8

Problem

There are n gas stations on a circular route. Station i provides gas[i] units of fuel, and driving from station i to station i + 1 (wrapping around) costs cost[i] units. Your car starts with an empty tank and has unlimited capacity.

Return the index of the starting station from which you can travel around the circuit once clockwise, or -1 if it is impossible. If a solution exists, it is guaranteed to be unique.

Examples

Input:  gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation: Start at 3: tank 4-1=3, +5-2=6, +1-3=4, +2-4=2, +3-5=0. Back at 3 with 0 >= 0.

Input:  gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation: Total gas 9 < total cost 10, so no start works.

Constraints

n == gas.length == cost.length
1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
The answer, if it exists, is unique.

💡 Key Insight

Let diff[i] = gas[i] - cost[i]. A full loop is possible iff sum(diff) >= 0. And if the tank goes negative while driving from start to station i, then no station between start and i can be a valid start either — each of them would begin with less fuel than we had when passing it (we arrived there with a non-negative tank). So we can jump the candidate start straight to i + 1, giving a one-pass greedy.

Brute Force Simulation

TimeO(n²)SpaceO(1).

Intuition

Try each station as the start and simulate the trip around the circle, failing as soon as the tank goes negative.

Algorithm

For each start in 0..n-1:
tank = 0; for k in 0..n-1: i = (start + k) % n, tank += gas[i] - cost[i]; break if tank < 0.
If the loop finished, return start.
Return -1.

Visualization

diff = gas - cost = [-2, -2, -2, 3, 3]

start 0: -2 < 0 fail
start 1: -2 fail
start 2: -2 fail
start 3: 3, 6, 4, 2, 0  -> never negative -> return 3

Code

java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            int k = 0;
            for (; k < n; k++) {
                int i = (start + k) % n; // wrap around the circle
                tank += gas[i] - cost[i];
                if (tank < 0) {
                    break;
                }
            }
            if (k == n) {
                return start; // completed the full loop
            }
        }
        return -1;
    }
}

Complexity

Time: O(n²) — up to n simulations of length n.
Space: O(1).

Minimum Prefix Sum

TimeO(n)SpaceO(1).

Intuition

Compute the running sum of diff starting from station 0. The point where this running sum is lowest is the hardest moment of the trip. If we instead start right after that lowest point, every later prefix is relatively higher, and the deficit we skipped is repaid at the end (assuming the total is non-negative). So the answer is the index just after the minimum prefix sum.

Algorithm

Walk i from 0 to n - 1 accumulating running += gas[i] - cost[i].
Track the minimum value of running and the index minIdx where it occurs.
If running (the total) is negative, return -1.
Return (minIdx + 1) % n.

Visualization

i         0    1    2    3    4
diff     -2   -2   -2    3    3
running  -2   -4   -6   -3    0
                    ^ minimum at i = 2  -> start = 3

Code

java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int running = 0;
        int minSum = Integer.MAX_VALUE;
        int minIdx = -1;
        for (int i = 0; i < gas.length; i++) {
            running += gas[i] - cost[i];
            if (running < minSum) { // lowest point of the trip so far
                minSum = running;
                minIdx = i;
            }
        }
        if (running < 0) {
            return -1; // not enough total gas
        }
        return (minIdx + 1) % gas.length;
    }
}

Complexity

Time: O(n) — one pass.
Space: O(1).

Greedy One PassOptimal

TimeO(n)SpaceO(1).

Intuition

Drive from a candidate start, keeping tank. If tank drops below zero at station i, every station in [start, i] fails, so reset start = i + 1 and tank = 0. Separately accumulate total over all stations. If total >= 0, the last candidate standing is guaranteed to complete the loop (the stations before it contributed a negative sum that the remaining surplus covers).

Algorithm

total = 0, tank = 0, start = 0.
For each i: d = gas[i] - cost[i]; total += d; tank += d.
- If tank < 0: start = i + 1, tank = 0.
Return total >= 0 ? start : -1.

Dry Run

flowchart LR
    S0["i=0, diff -2<br/>tank -2 < 0"] -->|"reset start = 1"| S1["i=1, diff -2<br/>tank -2 < 0"]
    S1 -->|"reset start = 2"| S2["i=2, diff -2<br/>tank -2 < 0"]
    S2 -->|"reset start = 3"| S3["i=3, diff +3<br/>tank 3"]
    S3 --> S4["i=4, diff +3<br/>tank 6"]
    S4 --> R["total = 0 >= 0<br/>return start = 3"]

Code

java

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0; // net gas over the whole circle
        int tank = 0;  // net gas since the current candidate start
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            int diff = gas[i] - cost[i];
            total += diff;
            tank += diff;
            if (tank < 0) {
                // no station in [start, i] can work; try the next one
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

Complexity

Time: O(n) — one pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force Simulation	O(n²)	O(1)
Minimum Prefix Sum	O(n)	O(1)
Greedy One Pass	O(n)	O(1)

Common Pitfalls

Resetting start to i instead of i + 1 — station i itself is part of the failing segment.
Forgetting the global total >= 0 check; the greedy's final start is only meaningful when the total is non-negative.
Worrying that start could become n: that only happens when total < 0 (the last segment was negative), in which case we return -1 anyway.
Comparing gas[i] >= cost[i] alone to pick a start — a station with a local surplus can still fail later.