[Solution]Problem 77: Gas Station [Microsoft]

Problem solving, greedy algorithms, cycles.

Mar 03, 2023

Hey, it’s your favorite cult leader here 🐱‍👤

On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those Leetcode-Style Interviews. 🔥🔥💹💹

To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

Help me buy chocolate milk

p.s. you can learn more about the paid plan here.

This can be a tricky problem if you don’t know what to look for.

In honor of those of you that struggled with this problem here is a meme to lessen your pain. To make the newsletter more fun to read, I am looking to throw in more memes/art/anything else. If any of you have anything to share, you can always reach me through my Instagram or other social media linked at the end of all my articles.

Alternative Caption- When your interviewer asks you to discuss Quantum Computing.

Back to the problem at hand.

This problem can be found as problem 134. Gas Station

Problem

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

You can test your solution here

If any of you would like to work one-on-one with me, feel free to reach out.

Step 1: Understanding the nature of this problem

Reverting to our mainstay, we will open by reading the problem very thoroughly and trying to tease out any hints about its nature. Let’s go through the problem, walk through the examples they gave us, and test out a few small test cases to create our baseline and build from there.

One of the first insights that pops out is this- it doesn’t matter how you got to a particular station. All that matters is the station you’re at and how much fuel you have left. This gives our problem a very recursive substructure. The more advanced amongst are probably perking up at this insight, because it means we can implement a very particular kind of algorithm- the greedy algorithm.

Some of you are probably underwhelmed by this. I told you this problem would be solved using a greedy algorithm. But no one explained why/how you would figure this out. And trust me I looked at a bunch of different solutions. This sucks because that won’t help you learn on a deeper level.

Fortunately, I have a guide- How to Spot Greedy Algorithms[Techinque Tuesdays]- to cover this topic. Use it to spot the greedy algorithms in your interviews/code challenges effortlessly.

The first hint that you can use to spot the Greedy Algos is their optimal sub-structure property. If your problem can be broken into sub-problems and that their individual optimal solution is part of the optimal solution of the whole problem, then the greedy algorithm is a viable solution.
-Make sure you read the guide if you struggle with spotting greedy algorithms in your Leetcode Interviews or day-day software engineering.

Now that we have that out of the way, how can we use this insight to build up our solution? Let’s proceed to the next step.

Step 2: The Greedy Approach

One of the reasons I love Greedy Algorithms is that they make life much easier to handle. The coding is generally very easy. The battle is won or lost in the spotting and the setup. We have already spotted the greedy algo, now let’s figure out a setup to solve it easily.

Our solution would look something like this: Starting from a station i, we add fuel from the station and attempt to travel to the next station (by subtracting the fuel remaining by the distance to the next station). There are two outcomes possible-

If the fuel is negative, we can't travel to the next station, so we have hit a failing case. In this case, we know that we can never get to the next station, starting from our current one. So we simply decide to start at the next station.
Otherwise, we continue our trip.

Here is a question for you? What if you start at i, go through i+1, and the next few stations, no problem? But you fail to go from station j to j+1? What should you do then? What station should we start from? Think about this, and proceed when you have an answer.

Step 3: Leveraging the Greedy Nature of our Problem

The answer is simple- we start from station j+1. Why? Think back to the setup. In a greedy problem, the individual optimal solution is part of the optimal solution of the whole problem. Once I have reached station j from i, then that is the optimal solution for that chord. We can never get to station j from a starting point b/w i and j with more fuel than if we started from station i.

We can prove this mathematically by using Case by Case Analysis, which I covered here. I’ll leave it to you since it will be good practice to help you develop mathematical rigor. The proof is fairly simple (in terms of knowledge requirements) and relies on your problem-solving skills. Here is a hint-

Hint- This can be proved using two cases: 1) We arrive at our station j with 0 fuel and 2) We come to station j with some leftover fuel. For further simplification, try to prove that the fuel from (j-2)→ (j-1)→j >= (j-1)→j. How does this extend to the general case?

Thus, when (fuel - cost[i+1]) becomes negative, we want to reset. What else can we do?

Step 4: Figuring out the Logistics

Since we are dealing with the difference in fuel and cost at any point, it makes sense to consider the difference between the two at any point. This will make our code much cleaner to read. Thus we open the code by applying the following preprocessing-

costDifference = [gas[i]-cost[i] for i in range(len(gas))]

costDifference[i] being negative tells us that it costs more to get to this station than the amount of fuel this will give us.

Applying this step in preprocessing, let’s us check for a simple base-case-

if sum(costDifference)<0: 
            return -1
else:
            currentSum = 0

Now technically you could smush the above two steps into one. This would bring your running time down since you’ll only be going through the list once. I kept them separate to make the work much more explicit.

With that check out of the way, we know that it is possible to do a cycle through the ring.

Next, we just need to loop through our differential list and implement the insights we picked up in the last step. I’ll let you work on that. When you’re done move on to the final solution

Step 5: Putting Everything Together

Our final solution will look like this-

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        costDifference = [gas[i]-cost[i] for i in range(len(gas))]
        if sum(costDifference)<0: 
            return -1
        else:
            currentSum = 0
        start = 0
        for i, diff in enumerate(costDifference):
            currentSum+=diff
            if currentSum<0:
                start = i+1
                currentSum = 0

        return start

Time Complexity- O(n)

Space Complexity- O(n)

Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.