O(n) time complexity Java Solution


  • 0
    C
    public class Solution {
    //O(n) time complexity solution
    //I can demonstrate that if the sum of diff equals to 0 or grater than 0, then
    //there is a start point where we can travel around the circuit once
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] diff = new int[gas.length];
        int total=0;
        //one pass to get the difference
        for(int i=0;i<gas.length;i++){
            diff[i] = gas[i] -cost[i];
            total+=diff[i];
        }
        if(total<0)
            return -1;
            
        //just one pass to solve this problem
        int sum=0;
        int start=0;
        for(int i=0;i<gas.length;i++){
            sum+=diff[i];
            if(sum<0){
                start = i+1;
                sum=0;
            }
        }
        return start;
    }
    

    }


Log in to reply
 

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