7/17/2020

[LeetCode] 134. Gas Station

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


DFS Solution ( Time Limit Exceeded ) 

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        
        def dfs(start, current, remain):
            if remain < 0:
                return False
            
            if start == current:
                return True
            
            return dfs(start, (current + 1) % len(gas), remain + gas[current] - cost[current])
        
        for i in range(len(gas)):
            if dfs(i, (i + 1) % len(gas), gas[i] - cost[i]):
                return i
        
        return -1
The DFS based solution will time out. However it reveals :
1. To finish a circle, the total gained gas must larger than total used gas
2. At each position, remained gas = last remained gas + gained gas - used gas. 
To reach to the next position, remained gas must larger than 0
If remained gas < 0, it means from the start position to current position, none of them can be used as start point. Because the initial remained gas of start position = 0

Greedy Solution

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # to finish a circle, gained gas must larger or equal to used gas
        total = 0
        
        # at each pos, remained gas = last remained gas + gained gas - used gas
        # if remained gas < 0, it means from start pos to current pos,
        # none of them can be used as start point.
        # because the initial remained gas of the start position = 0
        remain = 0
        
        start = 0
        
        for i in range(len(gas)):
            
            total += gas[i] - cost[i]
            remain += gas[i] - cost[i]
            
            if remain < 0:
                start = i + 1
                remain = 0
        
        
        return start if total >= 0 else -1

No comments:

Post a Comment