Another O(n) solution, easy understanding


  • 0

    Based on the idea of 53. Maximum Subarray, notice that we have a circle of gas stations, so we can apply one more pass to find the start point of contiguous gas stations that has the MaxPower within gas station circle.

    public int canCompleteCircuit(int[] gas, int[] cost) {
            int totalPower = 0, currentPower = 0,currentleft = 0;
    	int maxPower = Integer.MIN_VALUE, maxStart = 0;
    	for (int j = 0; j < 2*gas.length; j++) {
                    totalPower+=gas[j%gas.length]-cost[j%gas.length];
    		currentPower+=gas[j%gas.length]-cost[j%gas.length];
    		if (maxPower < currentPower) {
    			maxPower = currentPower;
    			maxStart = currentleft;
    		}
    		if (currentPower < 0){
    			currentPower = 0;
    			currentleft = (j+1)%gas.length;
    		}
    	}
            if(totalPower<0) return -1;
            return maxStart;
    }

Log in to reply
 

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