def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ if len(gas) == 0 or len(cost) == 0 or sum(gas) < sum(cost): return -1 position = 0 balance = 0 # current tank balance for i in range(len(gas)): balance += gas[i] - cost[i] # update balance if balance < 0: # balance drops to negative, reset the start position balance = 0 position = i+1 return position
Hi Stefan, sorry for the ambiguity.
By "one variable", I mean only using one variable to store the tank balance state. No need to use additional variables to store previous total amount like others' approach.
That "additional" variable is hidden inside
sum(cost) making in a
3*n algorithm instead of
1*n. Granted it's still
O(n), but usually I would choose one more variable and a condition over 2 full traversals.
@TWiStErRob You do realize that this approach can still be implemented in 2 traversals if we iterate over
len(gas) to find
sum(cost) instead of using
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.