Leetcode: Gas station
Given two arrays, gas and cost and an infinite tank, it costs costs[i] to go from one index to the other. The most a car can get gas is gas[i]. The task is to determine whether a car can go a full round for any possible starting point. The program should return the starting index if it is possible and -1 if it is not possible to do so.
Example:
gas = [1,1,2]
cost = [2,1,1]
# result: 22, because we can start from index 2, get 2 units of gas, and it costs us 1 unit to go to 1, leaving us with 1 unit. Then we can get another unit which is exactly the required 2 units it takes us to get to 1 and from there we get 1 leaving us with 0 at 2 and completing the cycle.
The initial solution that I came up with is listed below. For each possible starting point, calculate if we can reach the point again. This is not very efficient as it attempts to solve this problem for every possible starting point. This solution exceeds the runtime limit and is not successful.
from typing import List, Optional
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
def inner(g, c, start, balance):
if balance < 0:
return -1
if len(g) == 0:
return start
return inner(g[1:], c[1:], start, balance + (g[0]-c[0]))
for i in range(len(gas)):
g = gas[i+1:] + gas[:i] + [gas[i]]
c = cost[i+1:] + cost[:i] + [cost[i]]
if inner(g, c, i, gas[i] - cost[i]) > -1:
return i
return -1
if __name__ == '__main__':
s = Solution().canCompleteCircuit
print(s([1,2,3,4,5], [3,4,5,1,2]), 3)
print(s([2,3,4], [3,4,3]), -1)0 at any point in time the start index is not the correct one. Neither is any one of the indexes up to the current position and we can set the index to the next position. We set the running balance to 0. When we reach the end of the loop, we have to check if the total balance is above 0 to make sure that we are able to complete the loop. Otherwise we return -1.
from typing import List
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
gas_balance = 0
total_gas = 0
start_idx = 0
for i in range(len(gas)):
gas_balance = gas_balance + (gas[i] - cost[i])
total_gas = total_gas + (gas[i] - cost[i])
if gas_balance < 0:
gas_balance = 0
start_idx = i + 1
if total_gas < 0:
return -1
return start_idx
if __name__ == '__main__':
s = Solution().canCompleteCircuit
print(s([1,2,3,4,5], [3,4,5,1,2]), 3)
print(s([2,3,4], [3,4,3]), -1)
Runtime: 706 ms, faster than 91.03% of Python3 online submissions for Gas Station. Memory Usage: 19.1 MB, less than 75.91% of Python3 online submissions for Gas Station.