134. Gas Station

Hint

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        // If the total cost is greater than the total gas available,
        // it's impossible to complete the circuit, so return -1

        // Variables to track the starting gas station and the remaining gas

        // Iterate through each gas station
        for ()
        {
            // Update the remaining gas after reaching the current station

            // If the remaining gas is negative, we cannot reach the next station from the current start
            // So, reset the remaining gas and set the new start to the next station
        }
        // Return the starting gas station index
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
    {
        if (accumulate(cost.begin(), cost.end(), 0) > accumulate(gas.begin(), gas.end(), 0))
        {
            return -1;
        }
        int start = 0, remaining = 0;
        for (int i = 0; i < gas.size(); i++)
        {
            remaining += gas[i] - cost[i];
            if (remaining < 0)
            {
                remaining = 0;
                start = i + 1;
            }
        }
        return start;
    }
};

• T: $O(N)$
• S: $O(1)$