Ac solution code


  • 1

    The basic idea is checking the remaining gas after reaching each gas station by plusing (gas[i] - cost[i]).

    Greedy solution doesn't verify the remaining circular gas stations after n-1, because if total >= 0, then total(gas - cost) >= 0, which means the remaining trip after n-1 should have enough gas.That's the critical support for this one pass solution.

    Solution1. Greedy - Runtime = O(n)

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

    Solution2. Brute force(TLE Error) - Runtime = O(n^2)

    public int canCompleteCircuit(int[] gas, int[] cost) {
    	int n = gas.length;
    	for (int i = 0; i < gas.length; i++) {
    		int remaining = 0;
    		for (int j = i; j < i + n; j++) {
            	remaining += gas[j % n];
            	remaining -= cost[j % n];
            	if (remaining < 0)
            		return -1;
            }
    		return i;
    	}
        return -1;
    }

Log in to reply
 

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