Gas Station

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    n gas stations stand on a circular road. At station i you can pick up gas[i] units of fuel, and driving from station i to station i + 1 (from the last station back to station 0) burns cost[i] units. Your car starts with an empty tank of unlimited size. Return the index of a station from which you can drive all the way around once, or −1 if there is none. When a solution exists, it is unique.

    A greedy problem with a one-pass answer that sounds too simple until you can say why it works. Original problem: LeetCode 134.

    Example

    Starting at station #1 the tank reads 3, 0, 3, 3, 2 on arrival at each next station; it never goes negative, so the car makes it round.
    Starting at station #1 the tank reads 3, 0, 3, 3, 2 on arrival at each next station; it never goes negative, so the car makes it round.
    Input:  gas  = [2, 5, 1, 4, 3]
            cost = [3, 2, 4, 1, 3]
    Output: 1
    Input:  gas = [1, 2], cost = [2, 2]   ->  -1     # 3 units of gas, 4 needed

    Constraints (assumed)

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

    What this question tests

    • Reducing the problem to one array of gains gas[i] − cost[i].
    • The two greedy facts: enough total gas means some start works, and a failed run rules out every station inside it.
    • Turning an O(n²) simulation into one pass.

    Questions to ask first

    1. Is the answer unique? (Here: yes, if one exists.)
    2. Does the tank start empty? (Here: yes, and you fill up at the start station first.)
    3. Which direction? (Here: i to i + 1 only.)
    4. Is arriving with exactly 0 fuel OK? (Here: yes; only negative fuel fails.)