A simple O(n) solution


  • 0
    T
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int length = gas.length;
            int min = Integer.MAX_VALUE;
            int minIndex = -1;
            int sum = 0;
            for (int i = 0; i < length; i ++) {
                sum += gas[i] - cost[i];
                if (min > sum) {
                    min = sum;
                    minIndex = i;
                }
            }
            
            return sum >= 0 ? ((minIndex + 1) % length) : -1;
        }
    
    

Log in to reply
 

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