Gas Station

Time: O(n)

Space: O(1)

Intuition

If total gas >= total cost, a solution exists and is unique. Use a greedy scan: track running surplus; when it goes negative, the current starting station is impossible â€” reset to the next station.

Algorithm

1totalGas=0, currentGas=0, start=0.
2For i from 0 to nâˆ’1: totalGas += gas[i]âˆ’cost[i]. currentGas += gas[i]âˆ’cost[i].
3If currentGas < 0: start=i+1. currentGas=0.
4Return (totalGas >= 0) ? start : âˆ’1.

Example Walkthrough

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

1.i=0: cur=-2 < 0 â†’ start=1. i=1: cur=-2 < 0 â†’ start=2. i=2: cur=-2 < 0 â†’ start=3.
2.i=3: cur=3. i=4: cur=6. Total=2â‰¥0. Return start=3.

Output: 3

Common Pitfalls

•The existence of a solution is guaranteed when total gas >= total cost â€” only one valid start exists.

Gas Station.java

Java

// Approach: Greedy. If total gas >= total cost, a solution exists. Start from where cumulative tank first goes negative.
// Time: O(n) Space: O(1)
class Solution {
    public int startStation(int[] gas, int[] cost) {
        int n = gas.length;

        int sum = 0;
        int start = 0;
        int total = 0;

        for (int i = 0; i < 2 * n; i++) {
            int index = i % n;
            sum += gas[index] - cost[index];
            total += gas[index] - cost[index];

            if (sum < 0) {
                sum = 0;
                start = i + 1;
            }
        }

        return total >= 0 ? start % n : -1;
    }
}

Was this solution helpful?