Gas Station

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.

Naive Way: A brute force way is to start at each gas station and go as far as possible to see if the car can traversal through. That would be O(n^2) time complexity. The redundancy lies in that once you traversal far away starting from one gas station, the travel starting at next gas station can be predicted.

So the final approach is when the car fail at certain station, set the start point at the next station of that certain station. Because starting before that station would lead to failure at that certain station.

That makes the run time O(n), and O(1) space.

 public class Solution {  
   public int canCompleteCircuit(int[] gas, int[] cost) {  
     // edge case   
     if(gas.length==1) return gas[0] >= cost[0]?0:-1;  
     // genral case  
     boolean allVisited = false;  
     int i = 0;  
     while(i < gas.length){  
       // initialize tank  
       int j = (i+1)%gas.length;  
       if(j==0) allVisited = true; // check if all stations are visited  
       int tank = gas[i]-cost[i];  
       // travel as far as possible  
       while(tank >= 0){  
         tank += gas[j]-cost[j];  
         // check if meets start  
         if(j==i) return i;  
         // step forward  
         j++;  
         j %= gas.length;  
         if(j==0) allVisited = true;  
       }  
       // check ending condition  
       if(allVisited) break;  
       else i = j;  
     }  
     return -1;  
   }  
 }  

Improved Way: There is a better approach, just pick the i+1 -th  station on gas[i]-cost[i] = min(gas[j]-cost[j]) for all j. The solution is here.