Leetcode gas station

Question

I came across a gas station problem from leetcode. It can be solved in O(n) given the fact that, if started at station i, and when goes to the station j, there is not enough gas to proceed to the j+1 station, then none of the stations from i to j can be used as a starting point. In another post similar approach was provided.

I think the fact holds true with the assumption that the gas tank has unlimited storage. What if there is a maximum storage of the tank (i.e, if sum + gas[i] > MAXN, then sum = MAXN, otherwise sum += gas[i] in each station)? In such a case it is not necessarily true that none of the stations from i to j can be used as a starting point. Then is there still a O(n) solution to the problem?

Answer 1

In such a case it is not necessarily true that none of the stations from i to j can be used as a starting point.

Thats not true. Making more restrictions wont result in more possible starting points, it will result in less. The best candidate starting point is still the one returned by the original algorithm. If at any station you have full gas, and you run out of gas before you could finish a full circle, then there is no solution.

Lets assume the last station where you are at full gas is station i, and run out of gas at station i+k. That means, that between i and i+k stations, you always have at least 0 gas when you arrive. So if you had started there with 0 gas, you will run out of it anyway at station i+k. If you start at the i+k station, or any station after that, you will still run out of gas getting from station i to station i+k.

So to solve this problem, first find the best candidate station using the original algorithm, then from the resulting station go a second round and check if you can make it back to the starting point. If you cant, there is no solution.

The best solution of the original problem ensures that at every station you have the maximum possible gas. So if that starting point results in a successful circle, than all other starting points returned by the original algorithm will work too.

Edit:

To find other solutions, execute this after canCompleteCircuit (untested):

int findOtherSolutions(vector<int> &gas, vector<int> &cost, int bestStation, int totalGasLeft) {
  int sum = totalGasLeft;
  int min = totalGasLeft;
  vector<int> solutions;
  solutions.push_back(bestStation);
  for(int i = bestStation-1; i != bestStation ; --i){
    sum -= gas[i]-cost[i];
    if(sum <= min){
      min = sum;
      solutions.push_back(i); 
    }
    if(i==0){
       i = gas.size();
    }
  }
  return solutions;
}

Note that you will have to modify the canCompleteCircuit to get the total remaining gas:

int canCompleteCircuit(vector<int> &gas, vector<int> &cost, int &total) {
  int sum = 0;
  int j = -1;
  for(int i = 0; i < gas.size() ; ++i){
    sum += gas[i]-cost[i];
    total += gas[i]-cost[i];
    if(sum < 0){
      j=i; sum = 0; 
    }
  }
  return total>=0? j+1 : -1;
}

Answer 2

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int size = gas.length;
        for(int i=0;i<size;i++) {
            gas[i] = gas[i] - cost [i];
        }

        //try to find the start index which has the max addition value
        int index = -1;
        int maxLeft = -1;
        int left = 0;
        for(int i=size -1;i>=0;i--){
            left +=gas[i];
            if(left > maxLeft) {
                index = i;
                maxLeft = left;
            }
        }

        if(left < 0) index = -1;
        return index;
    }
}