[Google Question] Gas Station

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

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

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Example (taken from leetcode): 

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.

Approach: First approach that come to our mind is to treat every index as starting point and see if we can complete the tour but it will be expensive as it will take O(n^2) time. Here is how this approach looks like:

• FOR i = 0  To n - 1
• currGas = 0
• j = i
• isPossibleToMove = gas[i] >= cost[i]
• WHILE (isPossibleToMove)
• currGas = currGas + (gas[j] - cost[j])
• isPossibleToMove = currGas >= 0
• j = (j + 1) % n
• IF j == i AND isPossibleToMove
• RETURN i
• RETURN -1

Let's try to do better. We know that if Sum(gas) is grater than or equal to Sum(cost) then we can definitely complete the tour. We don't know where the starting point is but we are sure that there must exist at least one starting point from where we can complete the tour.

We also know that if gas[i] < cost[i] for any i then we can't start from i. We can generalize this fact as if currGasAmount at any station 'i' is less than 0 then we can say that one can't reach this station so we mark this as starting station. 

Please note that currGasAmount is the Sum(gas[0..i]) - Sum(cost[0...i]). Here is how this approach looks like:

• startStation = 0
• totalGas = 0
• currGas = 0
• FOR i = 0 to n-1
• totalGas = totalGas + (gas[i] - cost[i])
• currGas = currGas + (gas[i] - cost[i])
• IF currGas < 0
• startStation = i + 1
• currGas = 0
• IF totalGas < 0
• RETURN -1
• RETURN startStation

Now there might be a question in your mind that how we can say that starting station is k + 1 if currGas till kth station is negative. Let's prove it by contradiction:

Let's say our starting station is S(i). The algorithm above ensures that it is possible to go from S(i) to S(n) so we can say that there exist a station S(k) where 0 < k < i such that one can't reach S(k) from S(i).

Let's define a variable Gas(i) which is equals to gas[i]-cost[i]. 

First thing of which we are sure here is:

Sum(Gas(0)...Gas(n)) >= 0

We can write the above statement as:

Sum(Gas(0)...Gas(k)) + Sum(Gas(k+1)...Gas(i-1)) + Sum(Gas(i)+...Gas(n)) >= 0   (1)

Now we know that Sun(Gas(k + 1)...Gas(i-1)) is negative that's why our starting station is S(i). It could be 0 in case of k = i - 1. So we can say:

Sum(Gas(k + 1)...Gas(i - 1)) <= 0 (2)

According to (1) and (2):

Sum(Gas(0)...Gas(k)) + Sum(Gas(i)...Gas(n)) >= 0 (3)

Now because S(k) is unreachable from S(i), we can say:

Sum(Gas(i)...Gas(n) + Sum(Gas(0)...Gas(k)) < 0 (4)

If you look at (3) and (4), its a contradiction. Therefore the assumption that there exist a station S(k) where 0 < k < i such that one can't reach S(k) from S(i) is false.

That's all!

     

Implementation in C#:

    public int CanCompleteCircuit(int[] gas, int[] cost) 

    {

        int startStation = 0;

        int totalGas = 0;

        int currGas = 0;    

        for (int i = 0; i < gas.Length; ++i)

        {

            totalGas += (gas[i] - cost[i]);

            currGas += (gas[i] - cost[i]);

            if (currGas < 0)

            {

                startStation = i + 1;

                currGas = 0;

            }

        }

        return totalGas >= 0 ? startStation : -1;

    }

Complexity: O(n)