122. Gas Station

For each station, simulate the full trip around the circuit. If the tank never goes negative, that station is the answer.

Brute Force

Try starting at each station 0 through n-1. For each candidate start, simulate driving around the circuit: at each stop, add gas[i] and subtract cost[i]. If the tank goes negative at any point, this start does not work — move to the next candidate.

Two nested loops give O(n^2) time. Space is O(1) since we only track the current tank level.

Why it is slow: Each candidate start re-simulates the entire circuit from scratch, repeating work that a cleverer approach can avoid.

import java.util.*;

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0;
            boolean success = true;
            for (int j = 0; j < n; j++) {
                int station = (start + j) % n;
                tank += gas[station] - cost[station];
                if (tank < 0) {
                    success = false;
                    break;
                }
            }
            if (success) return start;
        }
        return -1;
    }
}

If total gas >= total cost, a solution must exist. To find it: scan once, tracking the current tank. Whenever the tank goes negative, the answer cannot be any station we have passed — reset and try the next station.

Mental Model

Imagine you are walking around the circular route with a running tally of (gas gained - cost spent). If the total around the full loop is negative, it is simply impossible. If it is non-negative, a valid start must exist.

The key insight: if starting from station s and driving to station j causes the tank to drop below zero, then no station between s and j can be a valid start either (they would have even less gas when reaching j). So we jump the candidate start to j + 1 and reset the running tank.

Algorithm Steps

1. Initialize total_surplus = 0, current_tank = 0, start = 0.
2. For each station i from 0 to n-1: a. Compute net = gas[i] - cost[i]. b. total_surplus += net (tracks feasibility). c. current_tank += net (tracks current attempt). d. If current_tank < 0: this start failed. Set start = i + 1 and reset current_tank = 0.
3. After the loop: if total_surplus >= 0, return start. Otherwise return -1.

Worked Walk-through

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

total_surplus = 0 >= 0, so return start = 3.

Why skipping works

Suppose starting at station s fails at station j (tank < 0). Every station s <= k <= j saw a non-negative tank when reached from s, meaning gas[s..k-1] - cost[s..k-1] >= 0. Starting at any k would miss that positive prefix and have even less gas at j. So no station between s and j can work.

Edge Cases

• Single station: gas = [5], cost = [4]. net = 1 >= 0, start = 0.
• Impossible trip: total gas < total cost. Return -1 immediately.
• All net-zero: gas = [2,2], cost = [2,2]. total_surplus = 0 >= 0, start = 0.

Complexity

• Time: O(n) -- single pass through the arrays.
• Space: O(1) -- three integer variables.