There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. 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
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.
Constraints:
gas.length == ncost.length == n1 <= n <= 10^50 <= gas[i], cost[i] <= 10^4
The description was taken from https://leetcode.com/problems/gas-station/.
#O(N) Time, O(1) Space
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) - sum(cost) < 0:
return -1 start, tank = 0, 0
for i in range(len(gas)):
tank += gas[i] - cost[i]
if tank < 0:
start = i + 1
tank = 0
return startThe problem asks us, if possible, to return the minimum index from the gas array that would allow us to make a circular trip through the gas stations.
Since there could be multiple indices where this constraint could be met, but we are being asked to return the first one, that is a strong indication that this will be a greedy problem. This is similar to the Jump Game problems.
This question comes down to two things, deciding whether a circular trip is possible and deciding where the first gas station is that will allow us to make this trip.
Deciding whether a trip is possible comes down to whether we can gain as much if not more gas than we will lose making the trip.
To find this, we can just return whether the amount of gas we are gaining subtracted by the amount of gas we are losing is greater than zero.
If it isn't, this circular trip isn't possible.
if sum(gas) - sum(cost) < 0:
return -1
Now that we know that the trip is possible, we can perform this same calculation on a smaller scale.
We will initialize our starting spot at the first gas station and our tank as empty.
start, tank = 0, 0
Then, for each gas station, we will pay the gas cost to make the trip to the next gas station and fill up with however many gallons we can there.
for i in range(len(gas)):
tank += gas[i] - cost[i]
If we have been left with an empty tank, then we know that everything up to here was a bad starting spot so we will set our starting flag to the gas station after this one and reset our tank to empty.
if tank < 0:
start = i + 1
tank = 0
The first valid starting point will be the gas station that we were able to receive more gas than we'd be expending getting there. Instead of picking the best gas station, we are basically eliminating the worst ones. Setting the starting flag to the next gas station is like saying, "We weren't able to make it here, let's try the next spot.". The first gas station that we were able to not, not start from is the one that we are able to start from.
return start