LC 0134 [M] Gas Station
Code with Senpai edited this page Jun 5, 2022
·
4 revisions
if we run out of fuel say at some i'th gas station, all the gas station between ith and starting point are bad starting point as well. because if we cannot make it from i'th gas station with a surplus, we never can make it with 0 starting tank.
if the surplus EVER becomes < 0, then we ran out of gas
we actually don't have to loop around to get the solution because there must be a solution is sum(gas) >= sum(cost) and the solution is unique, the first one that works
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total_surplus = 0
surplus = 0
start = 0
for i in range(len(gas)):
total_surplus += gas[i] - cost[i]
surplus += gas[i] - cost[i]
if surplus < 0:
surplus = 0
start = i + 1
return -1 if (total_surplus < 0) else start
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
n = len(gas)
surplus = 0
start = 0
for i in range(n):
surplus += gas[i] - cost[i]
if surplus < 0:
surplus = 0
start = i + 1
return start
footer