Share my O(n) Java solution with detailed proof


  • 0
    Z

    Let S be the running sum, set S = { s[0], s[1], s[2], ..., s[n] }.
    s0=a[0], sk = a[0] + ... + a[k], (k > 0, k <=n).

    If s[i] is the lowest element that less than 0, we want to proof that starting from gas station i+1 we can travel the circle once. In other words, we want to proof that the new running sums starting from i+1 always greater equal than 0.

    • Lets[i] is the lowest running sum, s[i] = a[0] + ... + a[i], (i >= 0) .
    • S'= {s'[0], s'[1], s'[2], ..., s'[n]}, s'[0] = a[i+1], with
    s'[k] = a[i+1] + ... a[i + k - 1], i + k -1 <= n.
    s'[k] = a[i+1] + ... a[n] + a[i+k-1-n], i + k - 1 > n.
    
    • Notice that s'[0] = a[i+1] = s[i+1] - s[i], so s'[k] can be rewritte as
    s'[k] = a[i+1] + ... a[i + k - 1] = s[i + k - 1] - s[i], i + k - 1 <= n
    s'[k] = a[i+1] + ... a[n] + a[i+k-1-n] = s[n] - s[i] + s[i+k-1-n], i + k - 1 > n.
    
    • For s'[0] = s[i+1] - s[i]>= 0 because s[i] is the lowest sum.

    • For i + k - 1 <= n, since s[i] is the lowest sum that less than 0, for all position j, there is s[j] >= s[i]. Thus, s'[k] = s[i + k - 1] - s[i] >= 0.

    • For i + k - 1 > n. because s[n] >=0 (Only when gas sum greater equal than cost sum will we have a solution). and s[i+k-1-n] >= s[i], move s[i] to the left hand side, - s[i] + s[i+k-1-n] >=0.

    • Both s[n] and - s[i] + s[i+k-1-n] are greater equal than zero, thus we can sum two equation together.

    • Therefore, s'[k] = s[n] - s[i] + s[i+k-1-n] >= 0.

    • In conclusion, all s'[k] >= 0, so starting from position right i + 1 next to lowest sum s[i] is the the valid starting gas station.

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int[] gains = new int[gas.length];
            int remSum = 0;
            int minGas = 0;
            int minIdx = 0;
            for(int i = 0; i < gas.length; i++){
                gains[i] = gas[i] - cost[i];
                remSum += gains[i];
                if(remSum < minGas){
                    minGas = remSum;
                    minIdx = i+1;
                }
            }
            if(remSum < 0)
                return -1;
            else 
                return minIdx % gas.length;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.