Gas Station

Greedy

25 min

Problem Statement

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.

Example

Example 1:

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

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

Output: 3

Solution

The greedy approach is to iterate through the gas stations and keep track of the current tank level. If at any point the tank becomes negative, it means we cannot reach the next station from the current starting point. In this case, we reset our starting point to the next station and reset the tank. If the total gas is less than the total cost, it's impossible to complete the circuit.

Algorithm Steps

If the total gas is less than the total cost, return -1.
Initialize `total` and `start` to 0.
Iterate through the gas stations.
Add the difference between gas and cost to the `total`.
If `total` becomes negative, it means we can't start from the current `start`. Reset `total` to 0 and set the new `start` to the next station.
Return the `start` index.

Gas Station

Greedy Approach

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

Output: -1

Progress1 / 1

Ready to start the visualization

Gas

Cost

Tank

Start Station

Gas Station Solution


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