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

  • 0

    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 {
            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;
                    if(flag) return i;
                return -1;

  • 0

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

  • 1

    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.