134. Gas Station

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:

• gas.length == n
• cost.length == n
• 1 <= n <= 10^4
• 0 <= gas[i], cost[i] <= 10^4

이 문제의 기본 아이디어는 surplus, deficit 이다. brute force 알고리즘으로는 $O(N^2)$ 에 풀 수 있다. 하지만 $O(N)$ 알고리즘도 존재하는데, 기본적인 아이디어는 surplus 와 deficit 과 startIndex 를 추적하는 것이다.

 

circle 을 잘 생각해보면 실패한 구간과 성공한 구간으로 나눌 수 있는데, 성공한 구간에서 남긴 잉여 연료가 실패한 구간에서의 부족분의 연료와 같거나 크다면 ($surpluse >= deficit$) 전체 circle 에 대한 완주가 가능하다고 볼 수 있다.

 

 

 

 

그렇다면 $surpluse >= deficit$ 이면서 나머지 구간에서 실패할 수는 없는것인가? 현재 위치에서 잉여량이 총 $deficit$ 보다 많음에도 나머지 구간에서 실패한다는 것은 나머지 구간의 어느 특정 노드에서 연료가 부족해 다음 단계로 못 나아가는 경우일 것이다.

하지만 구간별 $deficit$ 의 합은 $allDeficit$ 을 초과할 수 없으므로 이는 모순이 된다. 다음 그림을 살펴보자.

 

 

 

 

때문에 마지막 노드에서 $surpluse >= deficit$ 이라면 항상 시작 노드 startIndex 는 나머지 원을 완주할 수 있다.

 

 

그렇다면 $surpluse$ 가 최초 시작된 노드 이후의 노드가 startIndex 가 될 가능성은 없는 것인가?

이 또한 문제에서 답은 unique 하다고 명시했기 때문에 불가능하다. 예를 들어, 한 노드에서 surplus 가 시작되었고 다음 노드 또한 surplus 가 충분한 상황이 있을 수 있다면, 이러한 경우는 startIndex 가 여러개인 케이스가 되므로 문제의 조건에 위배된다.

 

## 참조

www.youtube.com/watch?v=nTKdYm_5-ZY&list=PLupD_xFct8mETlGFlLVrwbLwcxczbgWRM&index=8&t=0s