Straightforward Java Linear Solution with O(1) space, explanation and Math proof


  • 20
    P

    The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That's what the first loop does.

    If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station.

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int tank = 0;
        for(int i = 0; i < gas.length; i++)
            tank += gas[i] - cost[i];
        if(tank < 0)
            return - 1;
            
        int start = 0;
        int accumulate = 0;
        for(int i = 0; i < gas.length; i++){
            int curGain = gas[i] - cost[i];
            if(accumulate + curGain < 0){
                start = i + 1;
                accumulate = 0;
            }
            else accumulate += curGain;
        }
        
        return start;
    }

  • 0
    I

    I think there is a little bug here.The question asks to return the index from where we can complete a circuit.Lets say accumulate+curgain becomes <0 at start=3,then you check if you can start from start=4 and go till n-1(=gas.length-1).You should also be checking if you can go from n-1->1->2->3->4 completing the circuit which you are not doing.


  • 0
    P

    I understood your concern. Let's say if the car can not complete the entire circle, it will return -1 after the first loop. Right?


  • 0
    I

    No,what if when you have start=4 it fails at n-1->0.Then maybe start=5 is the answer and your code isnt leading to that.


  • 0
    I

    And I have seen atleast two more similar solutions in 'Discuss' so either I am missing something here or they have poor test cases for this question that are not able to show this mistake.


  • 3
    P

    Actually, that is implied with in the method. I'll give you the math proof.

    Let's say the length of the array is N, and gas[N-1] means the gas you can get from the last station, cost[N-1] means the cost of gas if you want to travel from the last station to the first station.

    Let's say a few more definition, just for convenience.

    g_i = gas[i], c_i = cost[i].

    A_i = g_i - c_i.

    Gain_i = A_i +...+ AN-2

    Gain_j = A_j +...+ AN-2

    Assumption : Gain_i + g_N-1 - c_N-1 < 0 and Gain_j + g_N-1 - c_N-1 > 0 and i < j and start = i

    Proof:
    Assume the assumption is true.

    1. As start = i
      => A_i + ... A_k > 0 for any k < N and k > i

    2. As Gain_i + g_N-1 - c_N-1 < 0 and Gain_j + g_N-1 - c_N-1 > 0
      => Gain_i + A_N-1 < Gain_j + A_N-1
      => Gain_i < Gain_j, and we know that i < j
      => A_i + ... + A_j-1 + A_j + ... + A_N-2 < A_j + ... + A_N-2
      => A_i + ... + A_j-1 < 0

     1. contradicts with 2. That means in no circumstance that we have accumulating positive gain from i to N-2 and fails at N-1 but succeed when accumulating from j, which j > i. 

  • 0
    I

    Much thanks for giving such a detailed analysis and clarifying the code.


  • 0
    P

    My pleasure.


  • 0
    N
    This post is deleted!

  • 0
    N

    what if all the cost[i]=gas[i], then you can start from any index?


  • 2
    I

    "The solution is giauranteed to be unique".Read the problem statement!


  • 0
    P

    How to make sure the updated start, i + 1, goes through all stations?


Log in to reply
 

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