Gas Station

MEDIUM✓ CHIP-TIMEDLC #134 — FULL STATEMENT ↗

The drill: Gas stations sit in a circle; each has fuel to give and a cost to reach the next one. Find the single station to start a full lap from with a tank that never runs dry — or report that none exists.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Gas stations are arranged around a circular route, each one offering some amount of fuel and charging some cost to drive to the next station in line. A car starts with an empty tank.

Choosing a station to start from and driving the loop in order, the tank gains that station's gas and then loses the cost to reach the next — the goal is finding a starting station from which the tank never dips below zero anywhere on the full lap.

If a valid starting station exists, this course guarantees it's unique — report its index. If no station works for a full lap, report that instead.

EX 01

gas = [2, 3, 4] · cost = [3, 4, 3]

→ -1

TOTAL COST EXCEEDS TOTAL GAS

EX 02

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

→ 4

TWO RESETS BEFORE THE WINNING START

EX 03

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

→ 3

THREE RESETS IN A ROW

stations form one circular route; the last connects back to the first
gas and cost values are non-negative, arrays the same length
the tank starts empty and must never go negative mid-lap
at most one valid starting station exists per input on this course

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Simulating a full lap from every candidate start re-walks the same circle n times. If a lap starting at station A fails partway at station B, what does that say about starting anywhere between A and B?

HINT 2 THE STRUCTURE

If the tank goes negative between A and B, no station from A up to B could have worked either — arriving at any of them mid-lap already means less banked fuel than starting fresh there. The whole block is disqualified at once.

HINT 3 ONE STEP FROM THE ANSWER

One pass: keep a running tank and a separate running total. Whenever tank dips below zero, the next station becomes the new candidate start and the tank resets to zero. If total gas ever meets total cost, the last candidate start is the answer; otherwise no station works.

COACH'S BOARD — THE PATTERN, STEP BY STEP

RESET ON EMPTYPATTERN · GREEDY — ONE PASSgas = [5, 1, 2, 3, 4] · cost = [4, 4, 1, 5, 1]

-3

-2

TANK / TOTAL

tank → 0

total → 0

STEP 1

Gas [5,1,2,3,4], cost [4,4,1,5,1] around a 5-station loop. Tank starts empty — one pass finds the start, resetting whenever it runs dry.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/gas-station.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total = tank = start = 0
        for i in range(len(gas)):
            diff = gas[i] - cost[i]
            total += diff
            tank += diff
            if tank < 0:
                start = i + 1
                tank = 0
        return start if total >= 0 else -1

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            ok = True
            for step in range(n):
                i = (start + step) % n
                tank += gas[i] - cost[i]
                if tank < 0:
                    ok = False
                    break
            if ok:
                return start
        return -1

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 15 LN

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

TIME O(N)SPACE O(1)JAVA · RACE PACE · 15 LN

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            long 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;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED