[LeetCode] 134. Gas Station (Medium/Python)

Gas Station - LeetCode

Above is the link to the problem.

 

Problem

There is a number of n gas stations along the circuit.

We can fill the gas amount of "gas[i]" at the i th gas station.

And it costs "cost[i]" of gas to travel from the i th station to its next i+1 th station.

Return the starting gas station's index if you can travel around the circuit once in the clockwise direction.

Otherwise, return -1.

You begin the journey with an empty and unlimited gas tank at one of the gas stations.

And the solution is guaranteed to be unique.

 

Example

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 units 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.

 

At first, I tried to solve the problem using 2 for loop O(n^2).

For finding the index of starting point,

and proofing the possibility that the car can pass all of the circuits.  

But the time exceeding problem had occurred.

So, I tried to solve the problem with less time complexity than O(n^2).

 

Code

 

 

Explanation

First, check the total filling gas amount and total using gas amount.

If filling amount < using amount, then we can't drive the circuits completely.

→ return -1 

But else, we have to think more details.

If there exist 5 gas stations that total filling amount ≥ total using amount.

We just check the state of the gas tank that has enough fuel to go next gas station from the first index.

If it is not enough, then make the gas tank to the initial state and start from the new index.

 

For example, if the gas tank state is negative(remaining gas in tank + filling amount at the gas station < using amount to go to the next station) at the ② index.

This means ①, ② can't be the answer.

Because ① can't satisfy the condition.

Starting from index ② also can't satisfy because it can't arrive at the index ③ although the remaining gas in the tank ≥ 0 (Remain gas from ①)

Therefore, we can make the gas tank to the initial(zero) state and assume that the travel starts from ③ index.

If the gas tank state is not negative until traveling to the last index ⑤ and the remaining gas is more than cost[⑤], then ③ is the unique answer for the starting point.

Why it can be possible?

Why we don't need to check that the gas is enough before index ③ despite it being called "circuit"?

Isn't there can exist a possibility of index ④ or ⑤ is a unique answer?

Let's think about this.

Think about the possibility that index ④ is the answer.

Let ④ be the unique answer of the problem.

But, starting from ③ index has more fuel than starting from ④ index. 

Because gas[③]>=cost[③] is self-evident from the gas tank state is not negative until the last index from index ③. 

And the remaining circuit is longer when starting from index ④ (①, ②, ③) than starting from ③ (①, ②).

(①, ②, ③) is also include (①, ②).

Therefore, starting from index ④ has to drive more than starting from index ③ with less fuel.

Maybe it is impossible because the answer is unique.