134. Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

My Answer 1: Wrong Answer (28 / 32 test cases passed.)

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

start 를 잡아줌

nextidx 로 다음 인덱스 값을 정함

tank < cost[nextidx] 이면 circuit 이 불가능하다 판단하고 -1 리턴
아니면 nextidx == start 일 때까지 계속 tank 값을 채워감

그냥 문제 이해를 못해서 안되는듯..^^

Time Complexity O(n), Space O(1)

Solution 1: Runtime: 52 ms - 73.62% / Memory Usage: 15.3 MB - 27.97%

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        if (sum(gas) - sum(cost) < 0):
            return -1
        
        gas_tank, start_index = 0, 0
        
        for i in range(len(gas)):
            gas_tank += gas[i] - cost[i]
            
            if gas_tank < 0:
                start_index = i+1
                gas_tank = 0
            
        return start_index

sum(gas) - sum(cost) < 0 일 때만 circuit 이 없나봄
그냥 0부터 시작해서 gas[i] - cost[i] 값들을 더해준다
gas_tank < 0 이면 start_index 를 옮겨주고 tank 를 비워줌

어떤 원리인지는 몰라도.. 신기