Gas Station

Problem

There are N gas stations along a circular route, where the amount of gas at station i as gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Solution

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas.length != cost.length) return -1;
        int sumGas = 0, sumCost = 0;
        int tank = 0, start = 0;
        for (int i = 0; i < gas.length; i++) {
            sumGas += gas[i];
            sumCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0; //We choose a new start, we need to empty car's tank  
            }
        }
        return sumGas >= sumCost ? start : -1; //Do not forget the "=" sign 
    }
}

Analysis

This is a greedy problem
The idea of this solution is that we have some vars to record the car's state during the loop
Inside for loop, we update the sumGas, sumCost, and tank with current i
If we notify that tank < 0, we need to update the start with the next i, cause this i as start won't work
And we also need to update the tank = 0 because we have chosen a new start, which means tank is brand-new
At the end, we need to check whether sumGas >= sumCost to return the correct result