Gas Station [LC#134]
There are n gas stations along a circular route, where the amount of gas at the
station i
isgas[i]
. You have a car with an unlimited gas tank and it costscost[i]
of gas to travel from the stationi
station to(i + 1)
. You begin the journey with an empty tank at one of the gas stations.Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.
Intuition: Greedy Approach
- Base case: If the total gas is less than the total cost, the circuit is not traversable. Otherwise, there is at least one valid starting point.
- If we had
tank
amount of gas before entering stationi
we can update the state astank += (gas[i] - cost[i])
. If we are starting fromi
, we settank = 0
. - We started from j and
tank
becomes negative at i, the segment [j,i] is not traversable starting with an empty tank. Additionally, none of the stations in that segment can be valid starting points as that would also lead to a negativetank
. - Therefore, the possible starting point is
i + 1
, and resettank
to 0 and re-check. - We are guranteed to find a starting point.
Code
def gas_station_valid_starting_point(gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
tank = 0
starting_index = 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
tank = 0
starting_index = i + 1
return starting_index
Time complexity
,