We start our journey at each gas pump and check whether we reach the starting pump or not, just see the code below to get the grasp of the approach used for this problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
for starting_pump in range(n):
tank = gas[starting_pump]
cost_to_next_pump = cost[starting_pump]
next_pump = starting_pump
while tank >= cost_to_next_pump:
tank -= cost_to_next_pump
next_pump = (next_pump + 1)%n
if next_pump == starting_pump:
return starting_pump
tank += gas[next_pump]
cost_to_next_pump = cost[next_pump]
return -1
|