O(n) java solution that beats 100% java coders as per the graph when I ran the code


  • -2
    S
    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if(gas == null || cost == null)
            return -1;
        if(gas.length != cost.length)
            return -1;
        int tracker = cost.length;
        int gRemain = 0;
        for(int i =0; i < cost.length; i++)
        {
            if(cost[i] > gas[i])
                continue;
            int j =i;
            tracker = cost.length;
            gRemain = 0;
            while(tracker>0)
            {
                if(cost[j] > gRemain + gas[j])
                    break;
                gRemain = gRemain - cost[j] + gas[j];
                j++;
                j = j%cost.length;
                tracker--;
            }
            if(tracker==0)
                return i;
            if(j > i)
                i =j;
            else
                return -1;
        }
        return -1;
        
    }
    }`
    

    Though it looks like that it has nested loops but it never traverse any element twice for wrong solution and hence it is not O(n2). since the solution is unique, the complete traversal is done only for required solution.


Log in to reply
 

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