My O(n) java solution (272ms)


  • 0
    K

    Hello guys,

    This is my O(n) Java solution that traverses the array only once, and requires (almost) no more additional space.

    public int canCompleteCircuit(int[] gas, int[] cost) {
           if (gas.length == 0)
                return -1;
    
            int startStation = -1;
            int prevMinDiff = 0;
    
            int totalDiff = 0;
            for (int i = 0; i < gas.length; i++) {
                int diff = gas[i] - cost[i];
                if (diff >= 0 && startStation == -1) {
                    startStation = i;
                    prevMinDiff = totalDiff;
                    totalDiff += diff;
                } else {
                    totalDiff += diff;
                    if (totalDiff < prevMinDiff)
                        startStation = -1;
                }
            }
            return (totalDiff < 0) ? -1 : startStation;
    }

  • 0
    S

    hi, i guess u just put the code in a wrong discussion page? your solution do not looks like solving two sum? if i am wrong, could just add some comment for me to understand?


  • 0
    K

    You are right. I moved it.


Log in to reply
 

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