Problem: (Gas station)
There are N gas stations along a circular route, where the amount of gas at station i is
gas[i].
You have a car with an unlimited gas tank and it costs
cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Solutions:
The first thought of this problem is to check whether there exists an index that can meet the requirement and check each of them in serial until we find one. Well, you will get a O(n^2) algorithm if you do so.
My second thought is, this problem can use dynamic programming to record the path in order to minimize the computation. However, it is still a O(n^2) algorithm.
After reading the solution of a guy from Leetcode.com, I realize that I went to the wrong way at the beginning. If we take a look at the problem, it is actually asking to "return ONE index that satisfy the requirement". Wow, I never notice that. So let's ask "What the most possible index?". If this index does not pass the constraints, there would no index left. As such, we only need to check the MOST POSSIBLE index and get a O(n) algorithm.
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
if (gas.size() == 0)
return -1;
int sum = 0;
int index = -1;
bool last = true;
for (int i = 0; i < gas.size(); i++) {
int diff = gas[i] - cost[i];
if (last && diff >= 0 && sum <= 0)
index = i;
last = (diff < 0);
sum += diff;
}
if (index == -1)
return index;
for (int i = 0, sum = 0; i < gas.size(); i++) {
sum += gas[(index + i) % gas.size()] - cost[(index + i) % gas.size()];
if (sum < 0)
return -1;
}
return index;
}
};