Gas Station — LeetCode 134 Python Solution

The problem

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.

Example

Input

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

Output

3

Explanation

Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4

Python solution

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        i = j = n - 1
        cnt = s = 0
        while cnt < n:
            s += gas[j] - cost[j]
            cnt += 1
            j = (j + 1) % n
            while s < 0 and cnt < n:
                i -= 1
                s += gas[i] - cost[i]
                cnt += 1
        return -1 if s < 0 else i

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 134. Gas Station is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems