**đźŹ—ď¸Ź** **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**

**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: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.