C++ O(n) two pointers solution


  • 0
    class Solution {
     public:
      int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int size = gas.size();
        int tank = 0, cnt = 0, start = 0, end = 0;
    
        while (cnt < size) {
          // when tank have fuel, we step forward
          while (tank >= 0 && cnt < size) {
            cnt++;
            end++;
            tank = tank + gas[end - 1] - cost[end - 1];
          }
    
          // when tank have no fuel, we step back and try to find a start point
          while (tank < 0 && cnt < size) {
            cnt++;
            start--;
            if (start < 0) start = size - 1;
            tank = tank + gas[start] - cost[start];
          }
        }
    
        if (tank >= 0) return start;
        return -1;
      }
    };
    

Log in to reply
 

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