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:
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.
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
.
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.