134.gas-station

math question, runtime 82.13 %

Solution 1:

This question is actually a math question. We have to know this:

If sum(gas) — sum(cost) > 0, there must have a start point to travel over the circuit. Otherwise, there is no such start point.

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) - sum(cost) < 0: return -1
        tank = 0
        start = 0
        total = 0 # accumulate total cost gas
        for i in range(len(gas)):
            tank += gas[i] - cost[i]
            if tank < 0:
                start = i + 1 # reset start only when tank < 0
                total += tank
                tank = 0
        if tank + total < 0:
            return -1
        else:
            return start
#   ✔ 31/31 cases passed (40 ms)
#   ✔ Your runtime beats 82.13 % of python3 submissions
#   ✔ Your memory usage beats 5.13 % of python3 submissions (14 MB)
#   ✔ 31/31 cases passed (40 ms)
#   ✔ Your runtime beats 82.13 % of python3 submissions
#   ✔ Your memory usage beats 5.13 % of python3 submissions (14 MB)