Gas Station

MediumGreedy

Given gas and cost at each station on a circular route, return the starting index to complete the circuit, or -1 if impossible.

Open problem

Constraints

1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4

Single pass with running tank

Time O(n)Space O(1)

If total gas is at least total cost, a solution exists. Track a running tank; whenever it goes negative, no station up to here can be the start, so reset the candidate start to the next station.

#include <bits/stdc++.h>
using namespace std;

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