Problem #134: Gas Station

Intuition & Strategy Breakdown

Greedily track net gas (gas - cost). If total gas < total cost, return -1. If current tank drops below zero at station i, reset starting station to i + 1.

Python Solution

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

Java Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0, totalCost = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i];
            totalCost += cost[i];
        }
        if (totalGas < totalCost) return -1;
        int currentGas = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            currentGas += (gas[i] - cost[i]);
            if (currentGas < 0) {
                currentGas = 0;
                start = i + 1;
            }
        }
        return start;
    }
}