Gas Station

medium array greedy

Problem

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

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

Output3

From index 3: tank runs 3, 7, 5, 4, 2 — never negative. From any earlier start, the tank dips below zero.

gas (comma-separated)

cost (comma-separated)

def can_complete_circuit(gas, cost):
    total = tank = 0
    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

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

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;
    }
}

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

Explanation

This looks like it might need trying every possible starting station, but a single greedy pass is enough. The whole idea rests on two simple facts about the gas/cost differences.

First, a full circuit is possible only if the total gas is at least the total cost — that is, the sum of all gas[i] - cost[i] is >= 0. We track this in total. If it ends up negative, the answer is -1.

Second, we track a running tank starting from a candidate station. The moment tank dips below zero at index i, no station from the current start up through i could have been the real starting point — so we reset start = i + 1 and set tank = 0 to begin fresh from the next station.

Why is the final start guaranteed correct when total >= 0? Because every stretch we abandoned had a negative sum, the leftover stretch after the last reset must have a non-negative sum, which means it can carry you all the way around.

Example: gas = [1,2,3,4,5], cost = [3,4,5,1,2]. The diffs are [-2,-2,-2,3,3]. The tank goes negative early and keeps resetting until index 3, where it stays non-negative; with total = 0 overall, the answer is start 3.

Time: O(n) Space: O(1)