Leetcode Study Day 8

Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
 

Constraints:

n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 104

My solution

My solution is complex and cost O(n^2) time complexity. It fails in the last two tests as the time exceed problem. Here is the fulle code with explanation:

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // An array to store the Ind that is not zero
        vector <int> maxInd;
        int n = gas.size();
        for (int i = 0; i < n; i ++){
            // if the difference is not zero, store the index to the vector
            if (gas[i] - cost[i] >= 0){
                maxInd.push_back(i);
            }
        }

        while (!maxInd.empty()){
            int maxIndLength = maxInd.size();
            // the index that want to check
            int targetInd = maxInd[maxIndLength-1];
            int current =  targetInd + 1;
            int currentGas = gas[targetInd] - cost[targetInd];
            // loop the array to find out if it can run in a circular route
            while (current != targetInd){
                // if go to the end of the array, return to 0 index
                if (current == n){
                    current = 0;
                    // if the 0 index is the target Index.
                    if (current == targetInd)
                        break;
                }
                // run and calculate the gas we have
                currentGas = currentGas + gas[current] - cost[current];
                // smaller than 0, means can't run the whole circle from this station
                if (currentGas < 0)
                    break;
                current ++;
            }
            if (currentGas >= 0)
                return targetInd;
            else
                maxInd.pop_back();
        }
        return -1;
    }
};

Improved Solution

The improved solution only cost O(n) time complexity.
The main idea is to make sure that the car have enough gas to run around the whole circuit, the total gas, which is the sum of all the gas[i] - cost[i], should be larger than 0. If it is smaller than 0, it means that the car can’t run around the whole circuit.

The second idea is to find out the gas station that can run the whole circuit. If the car can run from gasStation[i] to gasStation[i+1], it means that the car can run from gasStation[i+1] to gasStation[i+2]. So we can use a variable called currentGas to record the gas we have. If the currentGas is smaller than 0, it means that the car can’t run from gasStation[i] to gasStation[i+1], so we update the currentGas to 0 and update the gasStation to i+1.

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalGas = 0;
        int currentGas = 0;
        int gasStation = 0;
        for (int i = 0; i < n; i++){
            totalGas += (gas[i] - cost[i]);
            currentGas += (gas[i] - cost[i]);
            if (currentGas < 0){
                currentGas = 0;
                gasStation = i + 1;
            }
        }
        if (totalGas >= 0)
            return gasStation;
        return -1;
    }
};