yaox023's blog

Gas Station

Gas Station

yaox023's photo
yaox023
·

3 min read

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;
}
C++