134. Gas Station

leetcode.com/problems/gas-station/

Gas Station - LeetCode

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

노트 :

처음 접근 방식은 brute force로 start index를 바꿔가면서 체크하는 것이었음. 

여기서 중요한 포인트는 굳이 n^2번 돌지 않아도 된다는 것.

가스 스테이션을 다 돌기 위해서는 어쨌든 gas의 모든 합이 cost의 모든 합보다 커야한다는 속성을 사용.