[Google Interview] The Gas Station Problem – Be on the Right Side of Change

?️ Company Tags: Google, Facebook, Amazon

Are you gearing up for your coding interview? If your answer is yes, then here’s a very interesting interview question for you. Numerous programmers have claimed that they came across this interview question. Hence, there is a high probability that you might come across it as well in your interview. Will you be able to solve it optimally?

❖Problem Formulation

There are n gas stations along a circular route, where the amount of gas at the i^th station is gas[i]. You have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the i^th 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 of 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.

Note: If there exists a solution, it is guaranteed to be unique.

⚠️Constraints:

Both input arrays have equal lengths and are not empty such that the length(n) < 10⁴
Each element of the input array is a non-negative integer.

?Examples

Here’s an example to understand the problem:

✏️Example 1:
Input: 
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
Output: 3
Explanation:
We will start the trip at index 3 and fill up with 4 units of gas. Total fuel = 0 + 4 = 4
Next go to index 4. Total fuel = 4 - 1 + 5 = 8
Next go to index 0. Total fuel = 8 - 2 + 1 = 7
Next go to index 1. Total fuel = 7 - 3 + 2 = 6
Next go to index 2. Total fuel = 6 - 4 + 3 = 5
Next, go to index 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.

Graphical Illustration of the above example:

Let’s have a look at some other examples to improve our understanding of this problem.

✏️Example 2:
Input: 
gas = [2, 3, 4]
cost = [3, 4, 3]
Output: -1
Explanation:
We will start the trip at index 2 and fill up with 4 units of gas. Total fuel = 0 + 4 = 4
Next go to index 0. Total fuel = 4 - 3 + 2 = 3
Next go to index 1. Total fuel = 3 - 3 + 3 = 3
We cannot go back to index 2, as it requires 4 units of gas.
Therefore, we cannot complete the trip once hence we return -1.

✏️Example 3:
Input:
gas = [1, 3]
cost = [2, 1]
Output: 1
Explanation:
We will start the trip at index 1 and fill up with 3 units of gas. Total fuel = 0 + 3 = 3
Next go to index 0. Total fuel = 3 - 1 + 1 = 3
Next, go to index 1. The cost is 2. Your gas is enough to travel back. Therefore, return 1 as the starting index.

✏️Example 4:
Input: 
gas = [3, 4]
cost = [4, 5, 1]
Output: -1
Explanation: The length of the cost array is greater than the length of the gas array. Hence, it will return -1.

?️Brute Force Approach

Approach: In this method, we will start our trip at station i. Then, we will visit every station (go through every index) once. If we don’t have enough gas to get to the next station, we will start again at station i + 1. We will also keep track of the fuel in the tank at each index.

Let’s look at the code:

def gas_station(gas, cost):
    for i in range(len(cost)):
        count = 0
        fuel = 0

        for j in range(i, i + len(gas)):
            k = j % len(gas)
            fuel = gas[k] - cost[k] + fuel
            if fuel < 0:
                break

            count = count + 1

            if count == len(gas):
                return i

    return -1

Note: Using k = j % len(gas) helps to point to the right index.

Test Cases: Let’s run this code on our examples to check if it works.

# Example 1
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(gas_station(gas, cost))
# 3

# Example 2
gas = [2, 3, 4]
cost = [3, 4, 3]
print(gas_station(gas, cost))
# -1

# Example 3
gas = [1, 2]
cost = [2, 1]
print(gas_station(gas, cost))
# 1

# Example 4
gas = [3, 4]
cost = [4, 5, 1]
print(gas_station(gas, cost))
# -1

Hurrah! It passed all the test cases.

Complexity Analysis

Time complexity: In this method, we visit each station n times. Hence the time complexity becomes quadratic, i.e., O(n^2).
Space complexity: The space complexity remains constant, i.e., O(1) as this method does not takes up any extra space.

Discussion

In this method, we are using repetition. For example- there are 20 gas stations and we start the trip from the 10th gas station and discover that the car can’t go beyond the 15th gas station. Assume that the 16th gas station is the answer. In this case, we are doing repetitive work by calculating the gas required from the 10th to the 15th gas station again. So, can we optimize this? Is there a method that gives us a better complexity than O(n^2)?

?️Optimal Solution: Greedy Algorithm

Approach: In this approach, we will visit each index once while selecting which index is the best index to start the trip from. We know that a trip is possible only and only if the total gas of the trip is greater than or equal to the total cost of the trip. We also know that we can go from one station to another only when gas[i] – cost[i] >= 0. This implies that the fuel can never be negative and we need to restart as soon as this happens.

Let’s look at the exact algorithm to deepen our understanding:

Initialize a variable “begin” that will store the starting index of the round trip taken by the car. Initially, the fuel will also be 0.
While travelling to each station, update the fuel –
- fuel= fuel + gas[i] – cost[i]
If the fuel gets negative, restart the process again by choosing the next index as the starting point of the trip.
Lastly, return the “begin” variable if the total fuel available is greater than the total fuel burnt. Else return -1.

Let’s look at the code:

def gas_station(gas, cost):
    begin = 0
    total = 0
    fuel = 0
    for i in range(len(gas)):
        fuel = fuel + gas[i] - cost[i]
        if fuel < 0:
            begin = i+1
            total = total + fuel
            fuel = 0
    if total + fuel < 0:
        return -1
    else:
        return begin

Test Cases:

# Example 1
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(gas_station(gas, cost))
# 3

# Example 2
gas = [2, 3, 4]
cost = [3, 4, 3]
print(gas_station(gas, cost))
# -1

# Example 3
gas = [1, 2]
cost = [2, 1]
print(gas_station(gas, cost))
# 1

# Example 4
gas = [3, 4]
cost = [4, 5, 1]
print(gas_station(gas, cost))
# -1

Yeah! Our code passed all the test cases.

Complexity Analysis

Time complexity: As we go through the circuit only once in this method, the time complexity has now been reduced to O(n).
Space complexity: The space complexity remains constant, i.e. O(1) as this method does not takes up any extra space too.

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

✍️Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
So, do you want to master the art of web scraping using Python’s BeautifulSoup?
If the answer is yes – this course will take you from beginner to expert in Web Scraping.