Gas Station

The Gas Station seems like a fun one to try and tackle.

The challenge description:

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

Their example inputs and outputs describe it pretty well:

	

		

			Toggle
Numbering
			Copy
		
	

	
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
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.

Let’s think about it for a moment… Can we get around enough of the gas stations such that we don’t run out of gas?

What’s the limiting factor here? If we stall out at a gas station along our route, we know we can’t start there… or any of the ones we started with, right? Why waste computation for gas stations we know we can’t start from if we run out of gas on that route…

The trick to this question is as we’re running through the gas station list we have to keep track of two things, the total supply required at any given gas station and we’ll have to know what our current gas supply is.

Pseudo-pythonic-version might look something like this:

	

		

			Toggle
Numbering
			Copy
		
	

	
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # We can't make it around if the total gas is less than the total
        # cost, so we abort here
        if sum(gas) < sum(cost):
            return -1

        for every gas_station:
            update our total supply
            update the current amount of gas we currently have

            if the current supply dips below 0:
                set the starting gas station to the next one
                reset the current amount

        return the starting gas station if we have non-negative total supply

That seems pretty straight-forward, yeah? Let’s code it up:

	

		

			Toggle
Numbering
			Copy
		
	

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

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

            if current_supply < 0:
                starting_station = i + 1
                current_supply = 0

        return starting_station if total_supply >= 0 else -1

There we have it. Try it yourself!