My simple code with explanation


  • 0
    J

    Think in this way: first form an array p[] = gas[] - cost[]. Starting from any point, say i, that any value in sequence p[i], p[i]+p[i+1], .., p[i]+p[i+1]+...p[i-1] should be all non-negative. this sequence forms a graph. we call this sequence as s[i][...]. now the difference between s[0][...] and s[i][...] at each point is off set by a fixed amount of p[0]+p[1]+...p[i-1], EXCEPT the last point which is the same as sum of all points. so the problem is simplified to find i that p[0]+p[1]+..p[i-1] is minimum. Since the entire graph or s[i][...] is lifted by "-minimum", all points in s[i][...] EXCEPT the last one must be non negative. The last point is the sum, which has to be non-negative as well. Code as follows.
    '''
    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    if(gas.length == 0) return 0;

        int min = gas[0] - cost[0];
        int sum = min;
        int index = 0;
        
        for(int i = 1; i < gas.length; i++){
            sum += gas[i] - cost[i];
            if(sum < min){
                min = sum;
                index = i;
            }
        }
        if(sum < 0) return -1;
        return (index+1) % gas.length;
    }
    

    }
    '''


Log in to reply
 

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