23.01.07 Today’s Leetcode

134. Gas Station

처음에는 진짜 starting index마다 cycle이 가능한지 체크하는 방식으로 구현했으나, 그러면 time complexity가 O(n^2)이 되어버려서, 과감하게 포기하고 다른 방식을 생각해보았다. 아무리 생각해봐도 O(n)으로 가능한데, 결국 찾은 방식은 remain < 0이 될때, 즉 불가능한 index를 찾았을 때 그 index 다음부터 cycle이 가능한 index로 고려하는 방식이다.

class Solution:
    def check(self, gas, cost):
        remain = 0
        start = 0
        n = len(gas)
        for i in range(n):
            remain += gas[i] - cost[i]
            if remain < 0:
                start = i + 1
                remain = 0
        return start

    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if sum(gas) < sum(cost):
            return -1
        return self.check(gas, cost)