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

Gas Station: example test case

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.

Gas Station: example test case simulation

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

Gas Station: example test case simulation ends

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.

Gas Station: doubling to avoid circles

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.

Gas Station: starting the simulation

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.

Gas Station: restarting the simulation at index 1

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.

Gas Station: continuing the simulation from index 2 with the start index as 1

In the next station, we see something happen.

Gas Station: stopping the simulation at index 3 due to fuel shortage

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.

Gas Station: restarting from index i + 1 = 4

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.

Gas Station: continuing the simulation from index 4 with the start index as 4

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

Gas Station: reaching the index 9 with start index as 4.

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:

Gas Station: formalizing the 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
Avatar for Tanishq Chaudhary

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

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.