Gas Station

Problem#

gas[i] is fuel at station i; cost[i] is fuel needed to go from i to i+1 (mod n). Return the starting station for a full circular tour, or -1 if impossible.

Examples#

gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3
gas = [2,3,4], cost = [3,4,3] → -1

Constraints#

1 <= n <= 10^5.

Hints#

Hint 1

Tour is feasible iff total gas ≥ total cost. The starting index is the one right after the last “tank empty” point.

Approach#

Track total (overall surplus) and tank (running surplus since last reset). When tank < 0, reset start to i + 1 and zero tank. Final start is the answer iff total >= 0.

Solution#

class Solution {
public:
    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;
    }
};

func canCompleteCircuit(gas []int, cost []int) int {
    total, tank, start := 0, 0, 0
    for i := 0; i < len(gas); i++ {
        diff := gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0 {
            start = i + 1
            tank = 0
        }
    }
    if total < 0 {
        return -1
    }
    return start
}

from typing import List

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total = tank = 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 -1 if total < 0 else start

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

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

function canCompleteCircuit(gas: number[], cost: number[]): number {
    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 ? -1 : start;
}

Editorial#

Two facts make this O(n): (a) feasibility iff total surplus ≥ 0; (b) if tank goes negative at index j having started from s, no station in [s, j] can be a valid start — because starting from any of them would also hit ≤ that running deficit at j. So the next candidate is j + 1.

Complexity#

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

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#