Clean simple solution well-explained and accepted as best submission in C


  • 1

    Since we are required to find the only one available solution then we can just search for the most possible one first and then check its validity - bang, problem solved! Here is the basic idea:

    • there is a thing you need to remember that the circle is from i to i+1, so when we back check the most possible start index, we should start from the last gas station;
    • we are clear that once we pass one gas station we will get another refill gas[i]-cost[i] (this can be negative or positive);
    • in each gas station we can might encounter the max amount of remained gas to the last one and then we can update the maximal remained gas and record the index;
    • after traversing from the last to the first, we now get the maximal remained gas and the corresponding index and then we check it whether it's invalid - less than zero which means the circle can never be finished.

    //AC - 0ms;
    int canCompleteCircuit(int* gas, int gSize, int* cost, int cSize)
    {
        int index=-1, total=0, max=-1;
        for(int i = size-1; i > -1; i--)
        {
            total += gas[i]-cost[i];
            if(total > max)  index=i, max=total;
        }
        return total < 0? -1 : index;
    }

  • 0
    J

    Can you explain why it should start from the last ?

    I feel your explanation is not well explained for updating the index when a larger value is encountered.

    Thanks.


Log in to reply
 

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