O(n) java solution, no nested loop


  • 0
    M
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int i = 0;
        int deficit = 0;
        
        for(; i < gas.length; i++){
            int extra = gas[i] - cost[i];
            if(extra >= 0)
                break;
            else
                deficit -= extra;
        }
        
        if(i == gas.length)
            return -1;
        
        int tank = 0;
        int start = i;
        for(; i < gas.length; i++)
        {
            tank += gas[i] - cost[i];
            if(tank < 0){
                start = i + 1;
                tank = 0;
            }
        }
        
        if(start == gas.length || tank < deficit)
            return -1;
            
        return start;
    }

  • 0
    Y

    Let's say gas is {1,1,1}, cost is {1,100,1}. Apparently there's no solution, but your code will return 2. It does get AC though. Is it lacking test cases or am I misunderstanding the question?


  • 0
    X

    yes, you are right, there is no enough test cases, you can see my solution, that is correct.
    https://leetcode.com/discuss/33985/my-o-n-java-solution


  • 0
    M

    You are right, my previous solution was incorrect. This solution should work:

    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {

        int remaining = 0;
        int deficit = 0;
        int start = 0;
        
        for(int i = 0; i < gas.length; i++){
            int extra = gas[i] - cost[i];
            remaining += extra;
            
            if(remaining < 0){
                deficit -= remaining;
                remaining = 0;
                start = i + 1;
            }
        }
        
        if(start == gas.length || remaining < deficit)
            return -1;
            
        return start;
    }
    

    }


Log in to reply
 

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