Gas Station

This is a quite easy question. Actually, instead of "easy", I would rather say "smart". At first, you may wanna say just test each index, if a tour around the "circuit" can be complete, then return this index. Yes, this is not wrong. However, this might take too much time.  So, lets start from these potential sites, where gas[i] >= cost[i], so the car with empty tank can have enough gas to go to next station. Then, start from one of them, for instance site i, keep checking if car can go to j station, with total sum of gas is non-negative, if sum is smaller than 0 at site k, it means that starting from the index i is not a good choice. In this case, we need to find another potential site after k. Why not start over from i+1? Good question. For example, if we start from one site h between i and k, and gas[h] >= cost[h]. As we know, before arriving at h, sum must be larger than or equal to 0, even if this, sum get < 0 at site k. So if start from site h, sum definitely will get < 0. Thus it is useless to start from any sites between i and k, even if they are potential. So over and over again, we continue our process, until we find the index we want, or meet the end of array. If end was met, it means no suitable index has been found, return -1.

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas == null || cost == null) return -1;
       
        for(int i = 0; i < gas.length; ){
            if (gas[i] >= cost[i]){
                int tmpIdx = startTest(gas, cost,i);
                if (tmpIdx == i) return i;// car can go back to i , i.e. i is what we want
                else{
                    if(tmpIdx == -1) return -1;
                    else{
                        if(tmpIdx!= i)
                        i = tmpIdx;
                    }              
                }
            }
            else{
                i++;
            }
        }
       
        return -1;
    }
   
    public int startTest(int[] gas, int[] cost,int startIdx){
        int length = gas.length;
        int sum = gas[startIdx] - cost[startIdx];
        int i = startIdx + 1;
        i = i%length;
       
        while(i!=startIdx){
           
            sum += gas[i] - cost[i];
            if(sum < 0) break;// can't arrive at site i+1, or station i+1
            i++;
            i = i%length;
        }  
        if(sum < 0){// if failed
            i++;
            // i = i%length;
            while(i < length && i != startIdx){// find next potential index after i, where test failed
                if(gas[i] >= cost[i]) return i;
                else{
                    i++;
                    // i = i%length;                  
                }
            }
            // if can not find another potential index, then it is
            // not possible to complete the circuit
            return -1;
        }
        else return startIdx;
    }
}