Gas Station
Gas Station:
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:
n == gas.length == cost.length1 <= n <= 10^50 <= gas[i], cost[i] <= 10^4
Try this Problem on your own or check similar problems:
Solution:
- Java
- JavaScript
- Python
- C++
public int canCompleteCircuit(int[] gas, int[] cost) {
int tank = 0, acc = 0, idx = 0;
for(int i = 0; i < gas.length; ++i){
int diff = gas[i] - cost[i];
tank += diff;
acc += diff;
if(tank < 0){
idx = i + 1;
tank = 0;
}
}
return acc >= 0 ? idx : -1;
}
/**
* @param {number[]} gas
* @param {number[]} cost
* @return {number}
*/
var canCompleteCircuit = function (gas, cost) {
let tank = 0;
let acc = 0;
let idx = 0;
for (let i = 0; i < gas.length; i++) {
let diff = gas[i] - cost[i];
tank += diff;
acc += diff;
if (tank < 0) {
idx = i + 1;
tank = 0;
}
}
return acc >= 0 ? idx : -1;
};
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
tank = 0
acc = 0
idx = 0
for i in range(len(gas)):
diff = gas[i] - cost[i]
tank += diff
acc += diff
if tank < 0:
idx = i + 1
tank = 0
return idx if acc >= 0 else -1
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int tank = 0;
int acc = 0;
int idx = 0;
for (int i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i];
tank += diff;
acc += diff;
if (tank < 0) {
idx = i + 1;
tank = 0;
}
}
return acc >= 0 ? idx : -1;
}
};
Time/Space Complexity:
- Time Complexity: O(n)
- Space Complexity: O(1)
Explanation:
The brute force algorithm would run in quadratic time checking if any index is a good starting position (if we don't run out of gas), the trick to reducing time complexity to O(n) is to note following rules:
- If at the end the total sum of
gasis greater than thecostwe know we can go around at least one time, so we useaccto check if the total (sum) difference (between gas and cost) is greater or equal to0 - If we start at station
Athat can't reach stationE, but can reach stationsB, C, Dwe can prove by contradiction that none of the stationsB,C,Dcan reach stationEeitherA -> B -> C -> D E, for example if weBcan reachE, we already know thatAcan reachB, but that would mean now thatAcan reachE, which by the initial statement it can't, thus leading to contradiction. So, we could just skip all the stations on the path toE, and start withEas our first station while also restarting ourtank.