# Gas Station

·

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:

1. Is the station k is the answer?

2. 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;
}
``````