Simple C++ O(N) solution with explanation


  • 0
    C
    • I define need as how much gas we need to go to next station. It can be negative or positive.
    • I define start as the start station of this circle and i as the station trying to move forward.
      • if need > 0, that means we need gas, so we move backward trying to gain more gas.
      • if need <= 0, that means we get enough gas, so try to move forward.
      • if i == start, that means we have traveled a circle. we check need and return the result.
    class Solution {
    public:
        void decrease(int size, int &curr) {
            if (curr > 0)
                --curr;
            else
                curr = size - 1;
        }
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int size = gas.size();
            int start = 0;
            int need = 0;
            for (int i = 0; i < gas.size();) {
                if (need > 0) {
                    decrease(size, start);
                    need = cost[start] + need - gas[start];
                } else {
                    need = cost[i] + need - gas[i];
                    ++i;
                }
                #if 0
                cout<<"i: "<<i<<endl;
                cout<<"start: "<<start<<endl;
                cout<<"need: "<<need<<endl;
                cout<<endl;
                #endif
                if (i == start)
                    break;
            }
            if (need > 0)
                return -1;
            else
                return start;
        }
    };
    

Log in to reply
 

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