Back to DSA

Gas Station

medium
Acceptance: 43%
GreedyArrays

There are n fuel stations arranged in a circle. Station i offers gas[i] units of fuel, and traveling from station i to the next costs cost[i] units. Starting with an empty tank, determine the station index from which you can depart and complete a full loop, or return -1 if no such starting point exists.

Examples

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

Hints

Related Problems

Remove Duplicates from Sorted ArrayeasyBest Time to Buy and Sell StockeasyTwo SumeasyMerge Sorted ArrayeasyMove Zeroeseasy
00:00
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 ? start : -1;
    }
}
Time complexityO(n)
Space complexityO(1)