86. Gas Station

MediumGreedy & IntervalsAlso on LeetCode ↗

Stations on a circular route give gas[i]; driving from station i to i + 1 costs cost[i]. Starting with an empty tank, return the station index from which you can drive once around the circuit, or -1. The answer is unique if it exists.

Example 1

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

Output: 3

Example 2

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

Output: -1

Hint 1

If total gas ≥ total cost, a solution exists.

Hint 2

If you run dry at station i, no station between the current start and i can be the answer.

Greedy

Reference solution for One-pass greedy (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1                      # not enough gas in total
        start, tank = 0, 0
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:                   # cannot reach i+1 from `start`, nor from any station in between
                start, tank = i + 1, 0
        return 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++) {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) { start = i + 1; tank = 0; }
        }
        return total < 0 ? -1 : start;
    }
}

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

function canCompleteCircuit(gas, cost) {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) { start = i + 1; tank = 0; }
  }
  return total < 0 ? -1 : start;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

86. Gas Station

Example 1

Example 2

Approach 1: Simulate every start

Approach 2: One-pass greedy ✅