Skip to content
AI360Xpert
Back to Greedy
Medium

Gas Station

There are `n` gas stations along a circular route, where the amount of gas at the `ith` station is `gas[i]`. You have a car with an unlimited gas tank and it costs `cost[i]` of gas to travel from the `ith` station to its next `(i + 1)th` station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays `gas` and `cost`, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return `-1`. If there exists a solution, it is guaranteed to be unique.

Examples

Input:gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output:3
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.
Input:gas = [2,3,4], cost = [3,4,3]
Output:-1
You can't start at station 0 or 1, as there is not enough gas to travel to the next station. Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 3 + 2 = 3 Travel to station 1. Your tank = 3 - 3 + 3 = 3 You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3. Therefore, you can't travel around the circuit once no matter where you start.

Constraints

  • n == gas.length == cost.length
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4

Greedy Approach

Approach

First, check if a solution is possible: if the total gas is less than the total cost, we can never complete the circuit, so return -1. If `sum(gas) >= sum(cost)`, it's mathematically guaranteed that a unique solution exists. We can iterate through the stations, keeping a running total of our tank (`total = total + gas[i] - cost[i]`). If our tank becomes negative at any point, it means we cannot reach the next station from our current starting point. Furthermore, any station between our starting point and the current station is also invalid. So, we reset our tank to 0 and set the next station (`i + 1`) as our new tentative starting point.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) for computing the sum and doing one pass over the array. Space complexity is O(1) since we only use a few variables.

Solution.java
class Solution {    public int canCompleteCircuit(int[] gas, int[] cost) {        int totalGas = 0;        int totalCost = 0;        for (int i = 0; i < gas.length; i++) {            totalGas += gas[i];            totalCost += cost[i];        }                // If total cost is greater than total gas, impossible to complete the circuit        if (totalCost > totalGas) {            return -1;        }                int currentGas = 0;        int startIndex = 0;                for (int i = 0; i < gas.length; i++) {            currentGas += (gas[i] - cost[i]);                        // If tank is empty, we can't reach the next station from the current start            if (currentGas < 0) {                // Try starting from the next station                startIndex = i + 1;                // Reset current gas                currentGas = 0;            }        }                return startIndex;    }}