134.gas-station.md

134. Gas Station

Key Insights

1. Global Check

Question: Is it even possible? Image you could collect all the gass from all the statiions, if the total cost is more than the total gas, you can never make it, no matter where you start, you will simply run out of gas somewhere.

• Start from index 0:

totalGas =   gas[0] +  gas[1] + ... +  gas[n-1]
totalCost = cost[0] + cost[1] + ... + cost[n-1]
             ^^^^^^ ->

• Start from index 0 < k < n:

totalGas =   gas[k] + ... +  gas[n-1] +  gas[0] +  gas[1] + ... +  gas[k-1]
totalCost = cost[k] + ... + cost[n-1] + cost[0] + cost[1] + ... + cost[k-1]

Assume we can collect all the gas, the total gas and total cost are the same, no matter where you start.

Bank Account Analogy

Image the entire circular trip is 1-week-long trip:

• Each gas[i] is a paycheck you receive at day i.
• Each cost[i] is a bill you have to pay at day i.

You start with $0 money on day 0, the globak check (totalGas - totalCost) is simply asking one question at the end of the trip:

"After receiving all the paychecks and paying all the bills, do I have any money left?"

2. When Failed?

Core idea!! If starting from A fails at station i, then any station between A and i also be a invalid start.

Meaning: If we can't start from 0 → 3, then we definitely can't start from 1 → 3, 2 → 3, etc. Because starting from later means you have less gas to collect.

index  0  1  2   3
gas[i] 3, 2, 1, -7: 6 < 7
                 X
          2, 1, -7: 3 < 7
             1, -7: 1 < 7  

We started from 0 but failed at index 3 (3 + 2 + 1 < 7), that indicated that we also failed start from index 1 (throwing away +3, then 2 + 1 < 7) or 2 (throwing away +3, +2, then 1 < 7), because we have collected less gas from the later starting.

A             B             i
|-------------|-------------|
   segment 1     segment 2

假設從 A (起點) 出發，順利經過 B 站，最後在 i 站沒油停下來了。那麼：

1. 領先優勢：既然可以從 A 走到 B 站，代表 Net(A..B) >= 0，從 A 一路存夠「多餘的油」來到 B。
2. 在 B 繼續帶著「領先優勢」開往 i，最後還是在 i 失敗。帶著原本的領先優勢最後還是失敗了。
3. 如果我們改從 B 站出發呢？這時候油量是 0，相比剛剛從 A 到 B 時，少了 Net(A..B) >= 0，現在油更少了，更不可能走到 i 站。
4. 結論：一個帶著「領先優勢」的人在 i 站都破產了，那麼一個「白手起家」的人 (從 B 站出發) 只會更早破產。

證明:

• 既然 A 可以走到 B，代表 Net(A -> B) >= 0。
• 既然 A 無法走到 i，代表 Net(A -> B) + Net(B -> i) < 0 依照這樣我們來看，從 B 出發可以走到 i 嗎？也就是看 Net(B -> i) 是否是正或負。因為 Net(A -> B) 是正數，但是加上 Net(B -> i) 變成負數，那麼 Net(B -> i) 肯定是一個絕對值大於 A -> B 的負數，也就是 B 出發肯定也到不了 i。

Net(A -> B) + Net(B -> i) < 0
 positive      negative

Proof by contradiction

1. Assume there is some station B where A < B <= i that could be a valid start, we can start from B and complete the circuit.
2. Starting at A, we would arrive at B with positive gas (it's a valid start).
3. From B, we can finish the whole circle (by assumption).
4. That would mean starting from A also works. This is a contradiction: we know starting from A fails before station i.

Greedy

1. If the sum of gas is more thant the sum of cost, then there must be a solution.
2. The tank should never be negative, so restart whenever there is a negative number of tank.

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
    val n = gas.size
    var sumGas = 0
    var sumCost = 0
    var tank = 0
    var startIndex = 0
    for (i in 0 until n) {
        sumGas += gas[i]
        sumCost += cost[i]

        tank += gas[i] - cost[i]
        if (tank < 0) {
            startIndex = i + 1
            tank = 0
        }
    }
    
    return if (sumGas >= sumCost) startIndex
    else -1
}