My unique solution that finds the starting index first


  • 0
    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int startIndex = 0, maxDiff = 0, totalGas = 0, totalCost = 0;
            for (int i = 0; i < gas.length; i++) {
                totalGas += gas[i];
                totalCost += cost[i];
                if (cost[i] - gas[i] >= maxDiff) {
                    maxDiff = cost[i] - gas[i];
                    startIndex = i;
                }
            }
            if (totalCost > totalGas) return -1;
            while (cost[startIndex] > gas[startIndex]) {
                startIndex = (startIndex + 1) % gas.length;    
            }
            int gasRemain = 0;
            for (int i = startIndex; i < gas.length; i++) {
                gasRemain += gas[i];
                gasRemain -= cost[i];
                if (gasRemain < 0) {
                    return -1;
                }
            }
            for (int i = 0; i < startIndex; i++) {
                gasRemain += gas[i];
                gasRemain -= cost[i];
                if (gasRemain < 0) {
                    return -1;
                }
            }
            return startIndex;
        }
    }
    

    A little bit more verbose, but I think easier to understand. The starting index will always be the first index where there is more gas than cost, after the index with the maximum value of (cost - gas).

    It's easy to reason about. Since that station requires the "greatest" amount of gas, it makes sense that we reserve it for last. We search for the starting index in the beginning and then test afterwards.


Log in to reply
 

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