134. Gas Station
Problem:
There is a list of gas stations connected in a circular route. Each gas station has gas[i] amount of fuel, and it requires cost[i] to move to the next station. Print the index of the starting point from where it's possible to visit all gas stations without running out of fuel. If no such starting point exists, return -1. The starting point, if it exists, is unique.
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.https://leetcode.com/problems/gas-station/
What to learn:
Shift in thinking
Since the route of the gas stations is circularly connected, the indices can be reset from 0 using modulo operations. However, this approach results in a time complexity of .
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
for start in range(len(gas)):
fuel = 0
for i in range(start, len(gas) + start):
index = i % len(gas)
can_travel = True
if gas[index] + fuel < cost[index]:
can_travel = False
break
else:
fuel += gas[index] - cost[index]
if can_travel:
return start
return -1
If the total amount of gas is greater than the total cost, there must exist a starting point that can visit all stations. Given the constraint that the starting point is unique, there can only be one such point. Therefore, while visiting all stations, if a point is found not to be feasible as a starting point, the search for the starting point is moved back one station. If a point is found not to be feasible, then all points before it cannot be the starting point either.
Similar to proof by contradiction in mathematics, the starting point can be found by excluding points that are not feasible
Solution:
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
start, fuel = 0, 0
for i in range(len(gas)):
if gas[i] + fuel < cost[i]
start = i + 1
fuel = 0
else:
fuel += gas[i] - cost[i]
return start Last updated