134. Gas Station - cocoder39/coco39_LC GitHub Wiki

134. Gas Station

Initial thoughts:

• gas[start] - cost[start] must >= 0 so that the car can start
• to finish the trip, Sum(gas[i] - cost[i]) must > 0 for i from start to (i = N or 0 or start - 1)

Dig further:

• Suppose starting from A and B is the first station you cannot reach, then you cannot reach B from any station in between A and C Proof by contradiction: support C is between A and B so you can reach C from A. If you can also reach B from C then you can reach B from A.

• if Sum(gas[i] - cost[i]) >= 0 for i from 0 to n, then there must be a station that can satisfy the requirement proof by contradiction: Given 0 -> start-1 -> start -> n-1 where sum (start -> n-1) >=0 and sum(start -> n-1 + 0 -> start-1) >= 0 suppose exists k and sum(start -> n-1 -> 0 -> k) <= 0 we also have sum(start -> n-1 -> 0 -> k -> start -1) >= 0

so we can derive that sum(k -> start -1) >= 0. However, based on algorithm, start is the first that can reach n-1.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: 
        n = len(gas)
        total, tank = 0, 0
        start = 0
        for i in range(n):
            total += gas[i] - cost[i]
            tank += gas[i] - cost[i]
            if tank < 0:
                tank = 0
                start = i + 1
        return start if total >= 0 else -1