Problem Statement in English

There are n gas stations along a circular route, where the amount of gas at the i-th station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i-th station to its next (i + 1) % n-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.

Approach

To determine if there is a valid starting gas station, we can use a greedy approach.

The key idea is to keep track of the total gas surplus (gas - cost) as we iterate through the gas stations.

If at any point the total gas surplus becomes negative, it means we cannot start from any of the previous stations and reach the current station. Instead, we should reset our starting point to the next station.

If we reach the end of the array and the total gas surplus is non-negative, then the starting point we have recorded is the only valid starting station (since the question guarantees that there is only one).

If the total gas surplus for the entire trip is non-negative, then there must be a valid starting point, else we return -1.

Solution in Python


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1

        total = 0
        start = 0

        for i in range(len(gas)):
            total += gas[i] - cost[i]

            if total < 0:
                total = 0
                start = i + 1

        return start  # type: ignore

Complexity

  • Time: $O(n)$
    Since we are iterating through the gas stations only once.

  • Space: $O(1)$
    We are using a constant amount of space for the variables total and start.

Mistakes I Made

I had to look this one up :(

And we are done.