Gas Station | InterviewBit | Solution Explained

I explain the solution to Gas Station on InterviewBit using visuals in simple words.

0. Gas Station: Problem Discussion

0.0. IO Format

• input:
  • There are N gas stations along a circular route. Each has A[i] amount of gas.
  • To travel from station i –> i+1, there is B[i] cost.
• output:
  • Find the earliest station from where you can travel around the entire circuit.
  • Return -1 if not possible
• Constraints:
  • 1 ≤ N ≤ 1e6

0.1. Examples

Let’s say that we have the test case mentioned above. In that case, the earliest index that lets us travel in a circular route is 4. So, at index 4, we get 7 gas and spend 1 cost in going to the next station. That leaves us with a surplus of 6 units of gas.

And we iterate on and on till we get to 4 again.

At this point, we are done, and we can say that indeed, we can take a circular route and reach back the index 4.

1. Gas Station: Observations & Logic

1.0. Going in circles

One thing that might be tricky to handle is the fact that we are looking at a circular array. To make the implementation easier, we duplicate the arrays, like the following.

Note that the indices 5, 6, 7, 8, 9 are nothing but the indices 0, 1, 2, 3, 4 offset by 5 (which is the length of the array, N = 5).

Why do we do this? This makes the implementation simpler. If we want to check what happens at index 0, we can iterate and not worry about the circular looping and just check if we can reach the index 5 by simply iterating over the array. Note that index 5 is just the index 0.

We can say that for any index i in [0, N-1], we can find the stopping position in [N, 2N-1].

1.1. Bruteforce

All right. How do we start to think about a solution? Let’s start from the brute-force approach. We assume the answer is 0, that is, we can start at 0 and end at 5. We run a simulation to confirm it. The simulation takes O(N) time.

And since we do the simulation for every index till we find the index that works, we take O(N) to go over the indices as well.

Thus, the time complexity is O(N*N).

1.2. Simulation

Well, let’s actually assume we start at 0, and start to run a simulation. Maybe we will find something interesting as we go along.

At index 0, we see that the current is -1. This means that we do not have enough gas to allow us to go to the next index. What do we do?

Well clearly, this won’t give us the answer, so let’s restart at index i + 1 with an empty tank. Note the yellow circle represents the current assumed starting point.

So, now we have 3 extra gas, let’s continue on. 3 in hand, 2 we fill at the index 2 and 1 is the cost. Thus, the total becomes 4.

In the next station, we see something happen.

The curr becomes -4 at index 3, and that means we don’t have enough gas to go to the next.

So, let’s follow the if condition and move to station i + 1 = 4, assuming that is our start.

1.3. Hold up

Well … what about the stations 2 and 3?

Why did we skip from 1 straight to 4?

The answer to this holds the key to the greedy optimal solution.

Note how the simulation is reset as soon as we get curr < 0. That means the car passes form one station to the next if curr >= 0. In other words, we can say that the car accumulates fuel as we pass along the stations.

That means, if we start at 2 or 3, we are guaranteed to get worse answers.

Try it yourself, if you don’t believe me XD

1.4. Restart

All right, so let’s restart at index 4.

And now we keep on going and going, till the index 8.

After the index 8, we realize something. We have reached the index 9. Index 9 is nothing but the index 4! And that is what we have circled.

What does this mean? We have reached a solution. 4 is the final answer.

In summary, we have the following two rules:

And I promise, that is it!

2. Gas Station: Optimized Implementation

2.0. Code

class Solution:
    # @param A : tuple of integers
    # @param B : tuple of integers
    # @return an integer
    def canCompleteCircuit(self, A, B):
        n = len(A)
        
        curr = start = 0
        for i, (g, c) in enumerate(zip(A + A, B*2)):
            if i == start + n:
                return start

            curr = curr + g - c         
            
            if curr < 0:
                start = i + 1
                curr = 0
            
        return -1

2.1. Complexity Analysis

• Time: O(N), to iterate over the A and B arrays simultaneously in O(2N) time, or O(N). The 2N part is for doubling both the arrays.
• Space: O(1), we only store a bunch of variables

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.