LeetCode 134: Gas Station — Step-by-Step Visual Trace

#leetcode #python #algorithms

Medium — Greedy | Array | Simulation

The Problem

Find the starting gas station index from which you can complete a circular trip, where each station has gas to collect and cost to travel to the next station.

Approach

Use a greedy single-pass algorithm that tracks total gas deficit and resets the starting position whenever current gas becomes negative. If total gas is non-negative, a solution exists and the last reset position is the answer.

Time: O(n) · Space: O(1)

Code

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total_gas = 0
        current_gas = 0
        start_station = 0

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

            if current_gas < 0:
                start_station = i + 1
                current_gas = 0

        return start_station if total_gas >= 0 else -1