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+count1;
}
}
return 1;
}
};
My simple C++ O(n) solution


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.