134. Gas Station

time: O(n)

space: O(1)

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        for (int i = 0; i < gas.length; i++) { // check gas >= cost
            sum += gas[i] - cost[i];
        }
        if (sum < 0) return -1;
        
        sum = 0;
        int result = 0;
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            if (sum < 0) {
                sum = 0;
                result = i + 1;
            }
        }
        return result;
    }
}


/*
    g[1,2,3,4,5]
    c[3,4,5,1,2]
    
    g[i] - c[i] + g[i+1] >= 0
    
    0 + 3 - 4 < 0 => false,
    
    
    2,3,4
    3,4,3
    
    5-3 = 2
    2+4-4 = 2
    
    A <-> B fail => A 出發到 B fails
      A+1 A+2 < B => 從 A+1, A+2...< B 都會 fail
    
    so should use B+1 be a new start
    loop do this strategy, if following C point fails, use C+1 be a new start
    
    and until end, it finished 
    ( dont need to validate the follings in start of array, because 
    => If there exists a solution, it is guaranteed to be unique)
    
*/