LeetCode 134. Gas Station

Question

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 <= 105
• 0 <= gas[i], cost[i] <= 104

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

Solution

We can abstract this problem as following:

Given a delta array int[] delta, find a routine that sequentially traverses the array and makes the sum of $\delta$ always above or equal to zero during traversal, and return the start index of this routine. If there is no such routine, return -1.

There are two critical properities, we will prove and explain them later:

1. If $\sum_{i=0}^{n-1}{\delta_i} \ge0$, there must be at least one valid routine.
2. If $\sum_{i=p}^{q}{\delta_i} <0$ and $\delta_p \ge0$, any indice between $p$ and $q$ (inclusive) are not the start index of a valid routine.

According to these two properties, we just need to traverse the array twice, one for checking whether a solution exists, the other for finding the first solution.

Proof for the first property (Mathematical induction):

Proof for the second property (better to understand by intuition):

Note that just from the sum of the whole delta array, we cannot determine the number of solutions. Multiple solutions may exist when the sum is zero or greater than zero. For example, [1, 2, 3, 4] and [1, -1, 1, -1].

These two properties can also be used on many other situations.

// two-pass, can be merged into one pass
public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length;
    int totalTank = 0;
    // check if there is a solution
    for (int i = 0; i < len; i++) {
        totalTank += gas[i] - cost[i];
    }
    if (totalTank < 0) {
        return -1;
    }
    // if solution exists, find a solution
    int currTank = 0;
    int startIndex = 0;
    for (int i = 0; i < len; i++) {
        currTank += gas[i] - cost[i];
        if (currTank < 0) { // set i+1 as the start station and reset tank to zero
            startIndex = i + 1;
            currTank = 0;
        }
    }
    return startIndex;
}