Simple O(n) Java solution with comments


  • 7
    int canCompleteCircuit(int[] gas, int[] cost) {
    	int total = 0, tank = 0, index = 0;
    	for (int i = 0; i < cost.length; i++) {
    		int cur = gas[i] - cost[i];			
    
    		tank += cur;
    		if (tank < 0) {//if sum < 0, index can only start from i + 1
    			index = i + 1;
    			tank = 0;
    		}
    		total += cur;			
    	}		
    	return total < 0 ? -1 : index;
    }

  • 0
    S

    sorry to bother you. But I don't understand that if tank < 0 why index doesn't need to start from index + 1.


Log in to reply
 

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