Problem

Gas Station

Approach

  1. The easiest way is to use everyone element as the start and then check if it works. The time complexity is O(N^2), n to the second power.
  2. There is another method to solve it in O(N), one iteration.
    • First of all, we have to prove this conclusion that if the sum of all the gas minus all the cost isn’t less than zero, there must exist one solution. Following are using mathematical induction and the induction is the sum of all the gas minus all the cost isn't less than zero, there must exist one solution.
      • if there is only one element, it’s true.
      • if there are two elements, a and b, where gas(a) < cost(a), then gas(b) must be greater than cost(b). since gas(a) + gas(b) > cost(a) + cost(b), so b must be the start point.
      • if there are three elements, a, b and c, where gas(a) < cost(a), then: either if gas(b) < cost(b), then gas(c) > cost(c), so we can start at c and travel to a; since gas(b) < cost(b) and gas(c) + gas(a) > cost(c) + cost(a), we can continue to travel to b from a. or if gas(b) >= cost(b), we can travel from b to c. similar to the case above, we can reduce to the problem with two elements, b' and a', where gas(b’) = gas(b) + gas(c) and cost(b’) = cost(b) + cost(c). since gas(a) < cost(a), gas(b’) must be greater than cost(b’), so it’s same problem
    • Secondly, we can judge whether there is an answer or not by checking the value of sum mentioned above.
    • Thirdly, we can calculate the start index by checking if there is left gas in the tank

Code

class Solution {
    private boolean completeCircuitStartAt(int[] gas, int[] cost, int start){
        int N = gas.length, sum = 0;
        while(N >= 0){
            sum += gas[start] - cost[start];
            start ++;
            if(start == gas.length){
                start = 0;
            }
            if(sum < 0){
                return false;
            }
            N --;
        }
        return true;
    }
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for(int i = 0; i < gas.length; i ++){
            if(completeCircuitStartAt(gas, cost, i)){
                return i;
            }
        }
        return -1;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int N = gas.length;
        int sum = 0, curGas = 0, index = 0;
        for(int i = 0; i < N; i ++){
            sum += gas[i] - cost[i];
            curGas += gas[i] - cost[i];
            if(curGas < 0){
                curGas = 0;
                index = i + 1;
            }
        }
        if(sum < 0){
            return -1;
        } 
        return index;
    }
}