Problem statement

There are n gas stations around a circular route; station i has gas[i] fuel, and driving to station i+1 costs cost[i]. You start with an empty tank at some station.

Return the starting station's index from which you can travel around the circuit once clockwise — or -1 if impossible. If a solution exists, it is unique.

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3

Example 2

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1

Constraints

• 1 <= gas.length == cost.length <= 30
• 0 <= gas[i], cost[i] <= 20

Hints for Gas Station

1. Hint 1

   If total gas < total cost, the answer is -1; otherwise a unique start exists.

2. Hint 2

   If your tank goes negative arriving at i+1, no station ≤ i can be the start — restart from i+1.

How to solve Gas Station

Two independent facts settle this in one pass. First, a full loop is possible iff total gas is at least total cost — otherwise you run dry somewhere no matter where you begin. Second, if the tank goes negative on the way from start to i + 1, then no station in start..i can be the answer, so the search can skip straight past all of them.

Approach

1. Track total (overall gas minus cost) and tank (fuel since the current candidate start).
2. For each station i, add gas[i] - cost[i] to both.
3. If tank drops below zero, discard the current candidate: set start = i + 1 and reset tank = 0.
4. After the sweep, return -1 if total < 0, otherwise start.

Why it works

The skip is the interesting half. Suppose starting at start fails on the way to i + 1. Any station j strictly between start and i begins with an empty tank, whereas a run from start arrives at j with a non-negative tank — otherwise it would have failed earlier. So starting at j is no better and fails too. That lets one linear scan rule out whole blocks at once. And when total >= 0, the last surviving candidate must work, because every prefix discarded before it had negative sum, forcing the remainder to be non-negative throughout.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• You need both accumulators: tank finds the candidate, total decides whether an answer exists at all.
• Reset the tank to 0, not to the negative value, when moving the candidate start.
• Do not wrap around and simulate the circle — one linear pass is enough, and simulating is O(n^2).
• The problem guarantees uniqueness, so there is no tie to break.

Reference solution

Python

from typing import List

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

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium