Share my 8ms c++ solution, O(n) time and O(1) space.


  • 0
    L
    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int gas_amount = 0, cost_amount = 0, gas_amount_temp = 0, cost_amount_temp = 0;
            int start_station = -1;
            for(int i = 0; i < gas.size(); i ++)
            {
                gas_amount += gas[i];
                cost_amount += cost[i];
                gas_amount_temp += gas[i];
                cost_amount_temp += cost[i];
                if(gas_amount_temp < cost_amount_temp) 
                {
                    start_station = i + 1;
                    gas_amount_temp = 0;
                    cost_amount_temp = 0;
                }
            }
            if(gas_amount < cost_amount) return -1;
            if(start_station == -1) return 0;
            else return start_station;
        }
    };

  • 0
    B

    why don't initialize start_station = 0?


  • 0
    L

    Thanks for point out the problem. Initializing start_station = 0 is better.


Log in to reply
 

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