LeetCode - Gas Station
Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/gas-station
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 units of gas, but you only have 3.
Therefore, you can't travel around the circuit once, no matter where you start.
Constraints:
- gas.length == n
- cost.length == n
- 1 <= n <= 10^5
- 0 <= gas[i], cost[i] <= 10^4
Explanation
Brute force approach
The brute force solution is to consider every gas station as a starting point and see if there is a possible complete circuit.
To check every station, we would use two nested loops.
int start = 0;
int end = 1;
int current_petrol = gas[start] - cost[start];
while (end != start || current_petrol < 0) {
while (current_petrol < 0 && start != end) {
current_petrol -= gas[start] - cost[start];
start = (start + 1) % n;
if (start == 0)
return -1;
}
current_petrol += gas[start] - cost[start];
end = (end + 1) % n;
}
return start;The time complexity of the above approach is O(N^2).
Optimized solution
If we look at the problem, our point of concern should be the total amount of gas should be greater than the total cost. The only factor we need to consider is setting the starting point.
Let's jump to the algorithm directly.
- set current, total, start and diff to 0
- loop for i = 0; i < gas.size(); i++
- diff = gas[i] - cost[i]
- total += diff
- current += diff
// current value refers to the total gas - total cost till ith station.
// if that value is negative, this means gas is exhausted, and we cannot complete the circuit.
// Hence we set the current index as the start.
- if current < 0
- start = i + 1
- current = 0
- if total >= 0
- return start
- return -1
C++ solution
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int current = 0;
int total = 0;
int diff = 0;
int start = 0;
for(int i = 0; i < gas.size(); i++){
diff = gas[i] - cost[i];
total += diff;
current += diff;
if(current < 0){
start = i + 1;
current = 0;
}
}
if(total >= 0){
return start;
}
return -1;
}
};Golang solution
func canCompleteCircuit(gas []int, cost []int) int {
current, total, start, diff := 0, 0, 0, 0
for i := 0; i < len(gas); i++ {
diff = gas[i] - cost[i]
total += diff
current += diff
if current < 0 {
start = i + 1
current = 0
}
}
if total >= 0 {
return start
}
return -1
}Javascript solution
var canCompleteCircuit = function(gas, cost) {
let start = 0, diff = 0, total = 0, current = 0;
for( let i = 0; i < gas.length; i++ ) {
diff = gas[i] - cost[i];
total += diff;
current += diff;
if( current < 0 ) {
start = i + 1;
current = 0;
}
}
if( total >= 0 ) {
return start;
}
return -1;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]
Step 1: current = 0
total = 0
diff = 0
start = 0
Step 2: loop for i = 0; i < gas.size()
i < gas.size()
0 < 5
true
diff = gas[i] - cost[i]
= gas[0] - cost[0]
= 1 - 3
= -2
total = total + diff
= 0 - 2
= -2
current = current + diff
= 0 - 2
= -2
if current < 0
- -2 < 0
- true
start = i + 1
= 0 + 1
= 1
current = 0
i++
i = 1
Step 3: i < gas.size()
1 < 5
true
diff = gas[i] - cost[i]
= gas[1] - cost[1]
= 2 - 4
= -2
total = total + diff
= -2 + (-2)
= -4
current = current + diff
= 0 - 2
= -2
if current < 0
- -2 < 0
- true
start = i + 1
= 1 + 1
= 2
current = 0
i++
i = 2
Step 4: i < gas.size()
2 < 5
true
diff = gas[i] - cost[i]
= gas[2] - cost[2]
= 3 - 5
= -2
total = total + diff
= -4 + (-2)
= -6
current = current + diff
= 0 - 2
= -2
if current < 0
- -2 < 0
- true
start = i + 1
= 2 + 1
= 3
current = 0
i++
i = 3
Step 5: i < gas.size()
3 < 5
true
diff = gas[i] - cost[i]
= gas[3] - cost[3]
= 4 - 1
= 3
total = total + diff
= -6 + 3
= -3
current = current + diff
= 0 + 3
= 3
if current < 0
- 3 < 0
- false
i++
i = 4
Step 6: i < gas.size()
4 < 5
true
diff = gas[i] - cost[i]
= gas[4] - cost[4]
= 5 - 2
= 3
total = total + diff
= -3 + 3
= 0
current = current + diff
= 3 + 3
= 6
if current < 0
- 6 < 0
- false
i++
i = 5
Step 7: i < gas.size()
5 < 5
false
Step 8: if total >= 0
- 0 >= 0
- true
Step 9: return start
So the answer we return is 3.