Gas Station

Medium Subject: Greedy

Time Complexity

O(N)

Space Complexity

O(1)

Problem Description

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. Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Example 1:

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

Optimal Solution

Python

Approach: Greedy Single Pass

If total gas is less than total cost, return -1. Otherwise, a solution must exist. We iterate through the stations, maintaining a total_tank and curr_tank. If curr_tank drops below 0, we cannot start from the previous start index, so we reset start to i + 1 and reset curr_tank.

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:
                start = i + 1
                total = 0

        return start