My one pass solution.


  • 32
    class Solution {
    public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size=gas.size();
        int sum=0;
        int res=0;
        int total=0;
        for(int i=0; i<size; ++i){
            sum+=gas[i]-cost[i];
            if(sum<0){
                total+=sum;
                sum=0;
                res=i+1;
            }
        }
        total+=sum;
        return total<0?-1:res;
    }};
    

    The idea is simple.

    1. Whenever the sum is negative, reset it and let the car start from next point.
    2. In the mean time, add up all of the left gas to total. If it's negative finally, return -1 since it's impossible to finish.
    3. If it's non-negative, return the last point saved in res;

  • 8
    T

    Very nice solution above, here's a re-phrased version (in Java):

    • eliminating the need to total+=sum twice
    • self-documenting code with extra (sometimes redundant) inline comments

    private static final int EMPTY = 0;
    public int canCompleteCircuit(int[] gas, int[] cost) {
        assert gas != null && cost != null && gas.length == cost.length;
        int start = 0;
        int tank = EMPTY; // cumulated from station at start
        int total = EMPTY; // extra fuel left at the end of a full circle
        for (int station = 0, count = gas.length; station < count; ++station) {
            int fuel = gas[station] - cost[station]; // re-fuel and drive to the next station
            tank += fuel;
            total += fuel;
            if (tank < EMPTY) { // Ran out of gas on this circle starting from start, so
                tank = EMPTY; // we're starting again
                start = station + 1; // from next station.
                // We already left this station when run out of gas.
                // Starting anywhere (>= 0) up to this station would be futile,
                // because we'll run out of gas somewhere before this station.
            }
        }
        return total < EMPTY?
            -1 // cannot complete the full circle, because we would run out of gas somewhere
            :
            start // something is left in the tank so the last starting point is valid
        ;
    }

  • 0
    S

    if start = count, then your solution is incorrect.
    should be return total < 0 ? -1 : (start % count);


  • 0
    T

    @dr At the time of writing I tried and it was an accepted solution.

    Here's a take at reasoning: countth station is logically equivalent to the 0th station as you suggested with the modulus. Notice that start can only take the value of count if you run out of gas at the last station (count - 1), which means you couldn't complete the full circle from 0th station, hence you couldn't complete it starting from the countth station either, because they're "the same".

    Do you have an input for which it returns count?


  • 0
    S

    Thanks. I figured out that too.


Log in to reply
 

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