Class Solution

LeetCode_problems/Gas Station/solution.cpp:26–54

LOGIC: =================================================================================================== 1. We maintain two variables `surplus`, `deficit`, `start`. `surplus` - The amount of gas in tank for travelling to next station. `deficit` - The amount of gas that we are in shortfall. `start` - The potential starting station for the tour. 2. At anytime the current amount of gas `surp

===================================================================================================
*/
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        
        int n = gas.size();
        
	// Step - 1
        int surplus = 0, deficit = 0, start = 0;
        
        for(int i = 0; i < n; ++i){
            
            surplus += (gas[i] - cost[i]);
            
	    // Step - 2
            if(surplus < 0){
                deficit -= surplus;
                surplus = 0;
                start = i + 1;
            }
        }
        
	// Step - 3 (a)
        if(surplus < deficit)
            return -1;
        
	// Step - 3 (b)
        return start;
    }
};