[LeetCode] 134. Gas Station

Problem

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:

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

---

Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalSurplus = 0;
        int surplus = 0;
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            totalSurplus += gas[i] - cost[i];
            surplus += gas[i] - cost[i];
            if (surplus < 0) {
                surplus = 0;
                start = i + 1;
            }
        }
        return totalSurplus < 0 ? -1 : start;
    }
}

Explanation

• 주유소를 출발해 출발한 주유소로 다시 올 수 있다는 것은 각 주유소에서 충전할 수 있는 가스의 양과 소비되는 가스의 양의 차이인 흑자를 모두 더한 값이 0이 넘어야 하며, 이러한 흑자를 나타내는 값은 어느 주유소를 출발 기준으로 계산해도 동일하다.
• 위의 전체 흑자를 나타내는 값을 위해 변수 totalSurplus를 선언하고 for 반복문을 통해 전체 흑자값을 구하고 0이 넘지 않으면 -1을 반환하도록 if 조건문을 작성한다.

  int totalSurplus = 0;
  for (int i = 0; i < gas.length; i++) {
    totalSurplus += gas[i] - cost[i];
  }
  if (totalSurplus < 0)
    return -1;
  

• 출발 주유소 반환을 위해 변수 start를 선언한다.

  int start = 0;
  

• 어느 주유소에서 충전할 수 있는 가스의 양과 소비하는 가스의 양간 차이인 흑자가 0이 넘지 않으면 해당 주유소에서는 출발할 수가 없다.
• 위의 흑자 값을 나타내기 위해 변수 surplus를 선언한다.

  int surplus = 0;
  

• 흑자가 0을 넘지 못할 경우, 출발 주유소를 나타내는 start값에 해당 주유소 다음 주유소의 인덱스를 할당하도록 if 조건문을 작성하고, 한 주유소의 흑자를 나타내는 surplus값을 0으로 초기화한다.

  if (surplus < 0) {
    surplus = 0;
    start = i + 1;
  }
  

• 전체 흑자가 0을 넘지 못하면 -1을 반환하고, 그렇지 않으면 시작 주유소를 한바퀴 돌 수 있다는 의미가 되므로 출발 지점이 존재할 것이고, 그리하여 start를 반환하도록 한다.

  return totalSurplus < 0 ? -1 : start;