Friedrich Ewald My Personal Website

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: 2
The result is 2, 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)
A more elegant way of solving this is to try to start at the beginning and calculate the balance and the total balance in one iteration. If the balance goes below 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.


About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.