Night tankers run a ring of depots. Depot i sells gas[i] litres; the leg to the next burns cost[i]. The tank must stay non-negative for a full lap, and the board promises at most one origin that works. The intern nested a complete circuit from every start. Twelve depots returned. Four hundred depots on the coastal loop were still wrapping when the window closed.

Gas Station asks for the unique start that completes the circular route, or -1. Two arrays already give fill and burn per stop. Simulating a lap from every origin uses that and still pays n circuits. You are not asked for a path of tank readings.

The problem

Given int[] gas and int[] cost of the same length n, stations sit on a circle. From station i you fill gas[i], then pay cost[i] to reach (i + 1) % n. Return the starting index from which you can complete one full circuit without the tank going negative. If none exists, return -1. When a start exists, it is unique. You begin with an empty tank.

gas = [1, 5, 2],  cost = [2, 2, 3]   →  1
      net -1, +3, -1; total +1; only start 1 stays non-negative

gas = [4, 1, 3],  cost = [2, 3, 2]   →  0
      net +2, -2, +1; start 0 never dries

gas = [2, 3, 1],  cost = [3, 4, 2]   →  -1
      total -3; no origin can cover the ring

Note: The tank is checked after each leg, not after the fill alone. A station with gas[i] < cost[i] can still sit on a valid route if you arrive with leftover. The uniqueness promise is why one candidate is enough to return.

A full lap from every origin is the honest brute force

For each start, walk n legs with a running tank. The first time the tank drops below 0, that origin is dead. The first origin that survives the wrap is the answer. Correct. Quadratic.

int canCompleteBrute(int[] gas, int[] cost) {
    int n = gas.length;
    for (int start = 0; start < n; start++) {
        int tank = 0;
        boolean ok = true;
        for (int step = 0; step < n; step++) {
            int i = (start + step) % n;
            tank += gas[i] - cost[i];
            if (tank < 0) {
                ok = false;
                break;
            }
        }
        if (ok) {
            return start;
        }
    }
    return -1;
}

At a dozen depots this is a rounding error. At n in the hundreds you paid n circuits for a question one prefix answers: is the ring solvent, and where is the worst debt?

One pass: start after the worst prefix tank

Let net[i] = gas[i] - cost[i]. Sum every net. If the total is negative, the circle cannot close — return -1. Otherwise a unique start exists.

Walk once from index 0 with a running tank. Whenever tank goes negative at i, no start in the stretch you just abandoned can finish (that prefix already ran out). Reset: the next candidate is i + 1, and tank goes back to 0. That candidate sits immediately after the most negative prefix of nets.

You never wrap a second lap. The total check already paid for the circle. If the running tank never dips, start 0 is the origin.

gas = [1, 5, 2]   cost = [2, 2, 3]
net = -1, +3, -1     total = +1  (possible)

i=0  tank=-1  <0  start=1  tank=0     ← prefix from 0 is the worst debt
i=1  tank=+3
i=2  tank=+2
return 1

The Java is that walk:

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0;
    int tank = 0;
    int start = 0;
    for (int i = 0; i < gas.length; i++) {
        int net = gas[i] - cost[i];
        total += net;
        tank += net;
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    return total < 0 ? -1 : start;
}

Time is O(n) — one pass, constant work per station. Extra space is O(1) — three running integers. The nested lap is correct and the wrong bill once n leaves the toy range.

Note: If total >= 0, do not run a second lap. The uniqueness promise plus the prefix argument already picked the only origin that can finish. start == n can only happen when the last station still left the tank negative, which forces total < 0 and the -1 branch.

What interviewers usually poke next

  • Why the total check is enough. Every litre that exists is on the ring. If the sum of nets is negative, some leg is unpaid no matter where you begin.
  • Why you skip a whole prefix. If a walk from the current candidate first dries at i, every station in that candidate..i range already needed leftover you did not have. The next try is i + 1.
  • All nets zero, or one station. Start 0. The loop never resets. A single station with gas[0] < cost[0] is total < 0 and -1.
  • Two arrays vs one net array. You may allocate net[i] for the board; the intended loop does not need it. Overflow of gas[i] - cost[i] is not an int issue at typical bounds; name it if they widen the type.

You are done with this problem when you can walk [1, 5, 2] / [2, 2, 3] on a whiteboard with a running tank, and you can say out loud why n circuits are correct, why the total check kills the impossible ring, and why the start sits after the worst prefix debt.