134.Gas-Station.md

134. Gas Station

Difficulty: Medium

URL

https://leetcode.com/problems/gas-station/

Solution

Approach 1: Greedy

Find the rest of gas for each day (consider indepently). Then we do an accumulation to a partial sum that's non-negative, if we traversal the whole array and don't find an counter example which makes the partial sum to be negative, then we are happy and return the starting index. Otherwise keep updating the start index variable. (Trim first to avoid infinite loop, with a guaranteed solution)

The code is shown below:

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        rest = []
        for i in range(len(gas)):
            rest.append(gas[i] - cost[i])
        if sum(rest) < 0:
            return -1
        start_idx = 0
        count = 0
        cur_sum = 0
        while count < len(rest):
            cur_sum += rest[(start_idx + count) % len(rest)]
            count += 1
            if cur_sum < 0:
                # reset
                cur_sum = 0
                start_idx = (start_idx + count) % len(rest)
                count = 0
        return start_idx