Gas Station

Problem

There are n gas stations on a circular route. Given gas[i] (fuel you gain at station i) and cost[i] (fuel to travel from i to i+1), return the starting station from which you can complete the loop, or -1 if impossible.

Constraints

• n == gas.length == cost.length
• 1 ≤ n ≤ 10⁵
• 0 ≤ gas[i], cost[i] ≤ 10⁴

Approach — Greedy

This is a Greedy problem. The idea: make the locally best choice at each step, which provably builds up to the global optimum here. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log n) time.

Solution code

Python

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

Java

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 ? -1 : start;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.