Here's my code:
class Solution: # @param gas, a list of integers # @param cost, a list of integers # @return an integer def canCompleteCircuit(self, gas, cost): if len(gas) < 1: return -1 for i in range(len(gas)): count = 0 gas_total = 0 cost_total = 0 station = i while count < len(gas): gas_total += gas[station] cost_total += cost[station] if station == len(gas)-1: station = 0 else: station += 1 if gas_total < cost_total: break else: count += 1 if gas_total >= cost_total: return i else: continue return -1
Not the prettiest but it's the only way I can think of to express the logic that one should start at each station and keep a cumulative count of the gas obtained and expended, and that if at any point more gas has been expended than obtained, break out of the circuit and start over at the next station.
Is there a better (faster) way to express this logic? Or perhaps a simpler bit of logic to solve the problem altogether?
Your algorithm has a time cost of O(n^2), which is not necessary.
A better strategy (with O(n) cost) to tackle this problem is:
start from whatever station, complete the circle pretending you
car can still keep going with negative gas.
record the station at which your car has the lowest level of gas. ( that is the station
with the best chance to finish the circle).
record the final gas level when the circle is finished. if it is negative (means
sum(gas) < sum(cost)), then no solution is possible.
My code is attached :
class Solution: # @param gas, a list of integers # @param cost, a list of integers # @return an integer def canCompleteCircuit(self, gas, cost):
left = 0 lowlevel = 0 minindex = 0 n = len(gas) for i in range(n): left += gas[i] left -= cost[i] if (left<lowlevel): lowlevel = left minindex = (i+1) % n if left <0 : return -1 return minindex