My C++ solution, easy to understand


  • 0
    X
    class Solution {
    public:
    	int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    		vector<int> income;
    		for(int i = 0; i < gas.size(); i++){
    			income.push_back(gas[i] - cost[i]);
    		}
    
    	int sum = 0;
    	int start = 0, end = 0;
    	int n = 0;
    
    	while(start < gas.size()){
    		sum += income[end];
    		while(sum < 0 && start < gas.size()){
    			sum -= income[start];
    			start += 1;
    			n--;
    		}
    		end += 1;
    		end = (end == gas.size()) ? 0 : end;
    		n++;
    
    		if(n == gas.size())
    			return start;
    	}
    	return -1;
    }
    };

Log in to reply
 

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