Let's see the leetcode problem 134. Gas Station.

We can use brute force approach to start from each index and try to find the answer which has time complexity `O(N^2)`

, and of course the method will end up with time limit exceeded.

Now let's see how to do it with `O(N)`

.

Imagine the station is like below, the first station named as a and last station named as z.

```
[a, ...c, ...h, ...k, ...z]
```

Suppose we try from station a, and we pass some stations until station h. What information could be useful based on this try? Well, we have `a->h`

is not ok, we can deduce that `c->k`

is also not ok. Not only c, start from any station between a and h can be ruled out.

So, the only way out is to start from `h+1`

. Then with the same patterns, we go `h+1->k`

and we run out of cost, then we start from `k+1`

again. This pattern can be repeated multiple times, we can end up with multiple failed segments.

In the end, we will get a case, that we could start from one station and goes all the way into the end station. Let's say `k->z`

. What is this means? We may have a few questions:

Is the station k is the answer?

Could the stations between k and z be the answer?

Well, let's see question 2 first. If any stations between k and z could be the answer, which would lead to the fact the start from station k must also be an answer. This is in contradictory with the question description: it is guaranteed to be unique. So we can be sure that it is not possible that stations between k and z could be the answer.

Then we have only one question left, is the station k is the answer? Well it depends. Remember that before station k, we have multiple failed segements. Each segment is failed because of not enough gas. So to make the station k is the answer, we need to have gained enough gas betweens station k and station z. If the left gas is not enough to make up for previous segments, then there is no answer. If it is enough to cover, then station k is the answer.

Now we know the whole process, we can write code.

```
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
auto start_station{0};
auto current_gas{0};
auto total_gas{0};
for (int current_station{start_station}; current_station < gas.size();
current_station++) {
auto gain = gas.at(current_station) - cost.at(current_station);
current_gas += gain;
total_gas += gain;
// if current gas is below 0, then we should start from next station
if (current_gas < 0) {
current_gas = 0;
start_station = current_station + 1;
}
}
// is total gas is below 0, then it means cost is bigger than gas
if (total_gas < 0) return -1;
return start_station;
}
};
int main() {
vector<int> gas{1, 2, 3, 4, 5};
vector<int> cost{3, 4, 5, 1, 2};
Solution solution;
auto result = solution.canCompleteCircuit(gas, cost);
cout << result << endl;
return 0;
}
```