Gas Station

Medium Arrays & Hashing Kadane's Algorithm Original on LeetCode

Gas Station is a medium arrays & hashing problem solved with the kadane's algorithm pattern. The best approach, optimal (one-pass greedy), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (simulate every start) up.

Problem

There are n gas stations on a circular road. Station i gives you gas[i] units of fuel, and driving from station i to station i + 1 (the last one wraps to station 0) uses cost[i] units.

You start with an empty tank at a station of your choice, and the tank has no capacity limit. Return the index of the station from which you can drive once around the whole circle and come back to it, or -1 if that is impossible. When a valid start exists it is unique.

Examples

Example 1

Input: gas = [2, 1, 5, 4], cost = [3, 4, 1, 2]
Output: 2
Why: Start at 2: after each leg the tank holds 4, 6, 5, then 2, never going negative. Every other start runs dry.

Example 2

Input: gas = [1, 2, 3], cost = [2, 3, 2]
Output: -1
Why: Total fuel 6 is less than total cost 7, so no start can finish the loop.

Example 3

Input: gas = [6], cost = [6]
Output: 0
Why: One station: you fill up with 6 and the trip back to it costs exactly 6.

Constraints

n == gas.length == cost.length, 1 <= n <= 10^5
0 <= gas[i], cost[i] <= 10^4
If a valid start exists, it is unique.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (simulate every start)	`O(n²)`	`O(1)`
Optimal (one-pass greedy)	`O(n)`	`O(1)`

1Brute force (simulate every start)

TimeO(n²)Up to n starts, each simulated for up to n stations.

SpaceO(1)Only the tank and loop counters.

For each possible start, drive around the circle once, adding gas[i] - cost[i] at every station. The first start whose tank never drops below zero is the answer.

For start in 0..n-1: tank = 0.
For step in 0..n-1: i = (start + step) % n; tank += gas[i] - cost[i]; stop if tank < 0.
If all n steps completed, return start.
Return -1.

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int start = 0; start < n; start++) {
            int tank = 0, step = 0;
            for (; step < n; step++) {
                int i = (start + step) % n;
                tank += gas[i] - cost[i];
                if (tank < 0) break;
            }
            if (step == n) return start;
        }
        return -1;
    }
}

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        for start in range(n):
            tank = 0
            ok = True
            for step in range(n):
                i = (start + step) % n
                tank += gas[i] - cost[i]
                if tank < 0:
                    ok = False
                    break
            if ok:
                return start
        return -1

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int start = 0; start < n; start++) {
            int tank = 0, step = 0;
            for (; step < n; step++) {
                int i = (start + step) % n;
                tank += gas[i] - cost[i];
                if (tank < 0) break;
            }
            if (step == n) return start;
        }
        return -1;
    }
};

function canCompleteCircuit(gas, cost) {
    const n = gas.length;
    for (let start = 0; start < n; start++) {
        let tank = 0, step = 0;
        for (; step < n; step++) {
            const i = (start + step) % n;
            tank += gas[i] - cost[i];
            if (tank < 0) break;
        }
        if (step === n) return start;
    }
    return -1;
}

2Optimal (one-pass greedy)

TimeO(n)One pass over the stations.

SpaceO(1)Three counters.

Track the overall balance total and a running tank from the current candidate start. When tank goes negative after station i, no start up to i can work, so the candidate becomes i + 1 and tank resets. At the end, a non-negative total means the last candidate is the answer.

total = 0, tank = 0, start = 0.
For each i: d = gas[i] - cost[i]; total += d; tank += d.
If tank < 0: start = i + 1, tank = 0.
Return total >= 0 ? start : -1.

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 d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

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

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 d = gas[i] - cost[i];
            total += d;
            tank += d;
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
};

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

Edge cases to test

A single station
Total gas exactly equals total cost
The answer is the last station
Total gas smaller than total cost (answer -1)

Hints

Hint 1

If the total gas is at least the total cost, some start always works.

Hint 2

If you start at s and run dry right after station j, then no station between s and j can be the start either.

Hint 3

So scan once: whenever the running tank goes negative, restart from the next station with an empty tank.

FAQ

What is the best time complexity for Gas Station?

Optimal (one-pass greedy) runs in O(n) time and O(1) extra space. One pass over the stations.

Which pattern does Gas Station use?

It is a arrays & hashing problem that uses the kadane's algorithm pattern. Other problems with the same pattern: Kadane's Algorithm - Simple, Find minimum subarray sum, Kadane's Algo - Circular Array - No Extra Space.

Is there a brute force solution for Gas Station?

Yes. Brute force (simulate every start) takes O(n²) time and O(1) space. For each possible start, drive around the circle once, adding gas[i] - cost[i] at every station.

Which edge cases should I test for Gas Station?

A single station; Total gas exactly equals total cost; The answer is the last station; Total gas smaller than total cost (answer -1).