[LeetCode/Python] 134. Gas Station

Problem

[LeetCode]134. Gas Station

Solution

Trial #1

Code

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)

        for i in range(n):
            left = 0
            for j in range(i, i+n):
                j %= n
                left += gas[j] - cost[j]
                if left < 0:
                    break
            if left >= 0:
                return i
        return -1

• Time complexity: $O(n^2)$ → Time Limit Exceeded

Trial #2

Idea

• sum(gas) - sum(cost) < 0 → circuit impossible
• gas[i] - cost[i] < 0 → cannot start at station i
• tank = cumulative gain from start
  if tank < 0 at position j → must restart after j

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        total, tank, start = 0, 0, 0

        for i in range(n):
            gain = gas[i] - cost[i]
            total += gain
            tank += gain

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

        if total >= 0 and start < n:
            return start
        else:
            return -1