O(n) time, O(1) space, it is AC, but I am confused with the direction of the circle?


  • 0
    S
    class Solution {
    public:
         //why don't the car move from stations-1 to 0 (**anti-clockwise**)
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int stations=gas.size();       
            int cnt(1);                                         // the number of judging
            int tank(0), ode(0);                                //gas tank sum,  cost sum  from start to i
    
            for(int i=0, start=0; ; i=(++i)%stations){          // clockwise   from 0 to stations-1    
                if(ode!=0 && tank>=ode && i==start) return start;
    		    if(cnt==stations+1) return -1;
                
                tank+=gas[i];             
                ode+=cost[i];
                
                if(tank<ode){                     //reset start, tank gas sum, cost sum
                    tank=ode=0;
                    cnt++;
                    start=(i+1)%stations;
                }
                
            }
            
        }
    };

Log in to reply
 

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