My 8ms c++ solution with O(n) complexity


  • 0
    L

    Walk from i to j, when you find this path not valid, it means all points from i to j are not valid start points. Try the next point. When i >= n, quit!

       class Solution {
        public:
            int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
                int n = gas.size();
                for(int i = 0; i < n; i++){
                    bool flag = true;
                    int mygas = 0;
                    for(int j = 0; j < n; j++){
                        mygas = mygas +  gas[(i + j) % n] - cost[(i + j) % n];
                        if(mygas < 0){
                            i = i + j;
                            flag = false;
                            break;
                        }
                    }
                    if(flag) return i;
                }
                return -1;
            }
        };

  • 0
    A

    I think your complexity should be O(n^2).


  • 1
    L

    no, in worst case, it still only calculate n times, the second for loop should not be calculated into complexity. If I fail in this gas station, I'll start from the next gas station


Log in to reply
 

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