My solution is pretty straightforward, am I missing anything?


  • 5
    J

    My solution is accepted. The idea is if the sum of the gas is greater than the sum of cost, there must be a solution.

    Next, accumulate the "surplus" or "deficit" along the circle, at one point, you will have the biggest deficit. Starting from the next station, you will never run into deficit so you can travel around the circle.

    The solution is so straightforward, makes me wonder am I missing anything?

    Added: Proof of existence of solution when the sum of gas is on less than the sum of cost

    With that assumption, let's check the situation where there is only one station Greatest Net Deficit (GND)
    Note that the net surplus(NS) is the result of all the previous stations, a negative NS mean the car can not reach the next station.. If we start from the station from the station with the GND, which put the NS for that station at 0, then the NS will be positive for all station except the starting station, which can be positive or zero. Any way, the car can travel the circle.

    Next assume there are k station with equal GND, if we start from the first of them K1, we'll arrive in the next GND station K2 with 0 gas left, which means we can take K1-K2 path out of the circle without affecting our solution. Keep doing that we'll get back to the previous situation. So we know that there will be a least one solution given the sum of gas is greater than the sum of the cost.

     int canCompleteCircuit(vector<int> &gas, vector<int> &cost) 
    {
    
            int totalgas = 0;
            int totalcost = 0;
            int maxdiff = 0;
            int station = 0;
            int diff = 0;
            for (int i = 0; i < gas.size(); i++) {
                totalgas += gas[i];
                totalcost += cost[i];
                diff = totalgas - totalcost;
                if (diff < maxdiff) {
                    maxdiff = diff;
                    station = i;
                }
            }
            if (totalcost > totalgas)
                return -1;
            station +=1;
            if (station == gas.size())
                station = 0;
            return station;
            
        }

  • 0
    V

    I think your solution should be pretty good. If you can survive the biggest deficit, you can survive the rest.


  • 0
    W

    You intuition is correct and this is an elegant answer. We can show that the largest cumulative deficit occurs at station k, if k is the only solution. Now assume k is the solution:

    1. If k is the first station that we cannot reach from station 1, then that is the only cumulative deficit we see and therefor the largest.
    2. If we cannot reach k1 from 1, k2 from k1, ..., k from kn, since each interval has deficit, we will see the largest cumulative one at k (note starting from k we won't see deficit, otherwise k is not a solution)

  • 0
    J

    Thanks for your comment and I added a proof of the existence of the solution


  • 0
    O

    Good idea and decent code. I am not very clear about the proof though. Why do you choose GND as your startpoint of the proof? Suppose gas[]-cost[] = [-2, -1, 1, 2], what's the GND and where will you start the journey?


  • 0
    J

    I found a test case that your algorithm failed.
    int[] gas={3,1,2};
    int[] cost={1,3,2};
    the result should be 0, but the it returns 1.


  • 0
    H

    the initial value of maxdiff should be INT_MAX


Log in to reply
 

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