Easy to understand Java O(n) solution


  • 0
    L

    The basic idea is to start from the first index, check whether the remaining gas(gas-cost) is positive. If so, continue to the next index. If not, the starting index can only be the indexes after the current index. We allow the iterator to reach 2the length of array gas so that when the iterator meet with the starting index, we find a valid index. Otherwise, if the iterator exceed 2the length of the array, there are no valid staring index and we return -1. Here is my code in Java:

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            if(cost.length==0) return -1;
    		int remaining=-1;
    		int start_i=0;
    		int i=0;
    
    		while(i<2*gas.length)
    		{
    			int index=i%gas.length;
    			if(remaining<0)
    			{
    				if(gas[index]>=cost[index])
    				{
    					remaining=gas[index]-cost[index];
    					start_i=index;
    				}
    			}
    			else
    			{
    				if(start_i==index) return start_i;
    				remaining+=gas[index]-cost[index];
    			}
    			i++;
    		}
    		return -1;
    	}    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.