**🏗️** **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`

station is ^{th}`gas[i]`

. You have a car with an unlimited gas tank, and it costs `cost[i]`

of gas to travel from the `i`

station to its next^{th}` (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
^{4} - 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: 3Explanation:

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: -1Explanation: 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: 1Explanation: 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: -1Explanation: The length of the cost array is greater than the length of the gas array. Hence, it will return -1.

**🖊️****Brute Force Approach**

**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,**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**

While starting the trip, we have to select the best possible index, i.e., the index that can get the car to the next station(index). We know that if the car can always go to the next index, then the car will complete the trip. That means we have to check if the fuel of the tank allows the car to go to the next index. Hence, we can conclude that if the `gas[i] – cost[i] >= 0`

then that should solve our purpose.

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:is a critical life skill in today’s world that’s shaped by the web and remote work.**extracting data programmatically from websites** - 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.