My simple C++ O(n) solution


  • 5
    P
    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            vector<int> diff;
            int size = gas.size();
            for(int i=0; i<size; i++) {
                diff.push_back(gas[i]-cost[i]);
            }
            for(int i=0; i<size; i++) {
                if(diff[i]>=0) {
                    int sum = 0, count = 0;
                    while(sum>=0&&count<size) {
                        sum += diff[(i+count)%size];
                        count++;
                    }
                    if(count==size&&sum>=0) return i;
                    else i = i+count-1;
                }
            }
            return -1;
        }
    };

  • 0
    L

    I think this algorithm is not O(n) in time.


  • 0
    Y

    It is O(n) time complexity because there are two loops. The first one calculates the diff vector and the second one tries to find the start index. In the second loop, the variable count helps eliminate unnecessary steps because if a start index i makes the sum drop below zero, the next start index will be (i + count). Therefore, the worst case for the second loop will be n steps.


Log in to reply
 

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