[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:

・ gas.length == n
・ cost.length == n
・ 1 <= n <= 10⁵
・ 0 <= gas[i], cost[i] <= 10⁴

Idea

우선 Circuit 전체를 돌 수 있는지 확인해야 한다. 주어진 gas station에서 보충할 수 있는 연료의 합이 circuit을 도는 데 사용하는 연료보다 크거나 같은지 확인하고, 만약 작다면 곧바로 -1을 리턴하면 된다.

이후에 startPoint를 확인하는 것이 관건이다. Gas station을 방문하면서 현재 가지고 있는 연료의 양을 확인하고 만약 0보다 작다면 startPoint를 현재 gas station의 다음 gas station으로 설정한다. 이는 이전 startPoint와 현재 조건이 어긋난 gas station 사이의 어떤 지점을 선택해도 충분한 연료를 얻을 수 없기 때문이다.

전체 gas station을 탐색한 뒤 startPoint로 설정되어 있는 값을 리턴하면 된다. (time complexity: O(n))

처음에 O(n²)으로 풀다가 Time Exceeded 떠서 풀이를 봤다 😱

Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int tank = 0;
        for(int i = 0; i < gas.length; i++)
            tank += gas[i] - cost[i];
        if(tank < 0)
            return - 1;

        int start = 0;
        int accumulate = 0;
        for(int i = 0; i < gas.length; i++){
            int curGain = gas[i] - cost[i];
            if(accumulate + curGain < 0){
                start = i + 1;
                accumulate = 0;
            }
            else accumulate += curGain;
        }

        return start;
    }
}

Reference

https://leetcode.com/problems/gas-station/