134. Gas Station Leetcode Java

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Solution:

This problem is a very good problem and really need some critical thinking. 

Some observation here:

Set budget[i]=gas[i]-cost[i]

1.If budget[i]<0 => we can't go to (i+1)th gas station.

2. If Sum(budget[i]:budget[j])<0 we can't go to j from i.

3. If Sum(budget[0]:budget[n])<0, we can't make a cycle.

Those are some obvious observations, Following are some patterns behind the scene. 

1.If we calculate sum(budget[i]: budget[j]) until sum becomes negative, which means sum(budget[i]:budget[j-1])>=0 but sum(budget[i]:budget[j])<0, the car can't go from i to j and it can't go to j from any point between i and j-1, because it is station j make the summation negative, so any station between i and j-1, let's say x will make sum(budget[x]:budget[j])<0. In addition any station between i and j can't be the starting point because they can't even reach j. The starting point must between j+1 and n.

2. According to the previous conclusion, we can divide the cycle to several pieces, first couple pieces contain a negative sequence so that sum(budget[start]: budget[end])<0. And the last piece contains a positive sequence to make it reach to n (if there is no such positive sequence end at n, it definitely can't make a cycle). Assume the cycle has been divided to those pieces: 0-> i1 (negative, i1 can be 0); i1+1->i2(negative); i2+1-> i3(negative); i3+1 -> n (positive). Let's set the sum of the 3 negative sequences as negSum, and the sum of budget[i3+1]->budget[n] as posSum, if posSum+negSum>0, which means, we can start from i3+1 ->n->0->i1->i2->i3->i3+1, because the posSum will compensate each negative sequence and still can reach itself. 

The algorithm is a little greedy here, we sum the budget for every station, if the sum becomes negative, we know the start point won't be any station before the current station. 

And we can know this is a negative sequence, add the sum to negSum. Unless we can find a station that can reach n, that station is a valid candidate of making a cycle. The last step is to check if the gain can from start to n can compensate the loss from 0 to start. 

Time complexity: O(n)

  public int canCompleteCircuit(int[] gas, int[] cost) {  
    if(gas==null || gas.length==0 || gas.length!=cost.length) return -1;  
    int start=0;  
    int posSum=0;  
    int negSum=0;  
    for(int i=0;i<gas.length;i++){  
      int budget=gas[i]-cost[i];  
      posSum+=budget;  
      if(posSum<0){  
        negSum+=posSum;  
        posSum=0;  
        start=i+1;  
      }   
    }  
    return (negSum+posSum>=0)? start:-1;  
   }