[LeetCode] Gas Station (Java)

There are N gas stations along a circular route, where the amount of gas at station i is 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.

Firstly, I use dynamic programming to solve this problem. I define S[i,j] as the gas left when I start from i and finally reach j. And if S[i,j]<0, S[i,k] will be smaller than 0, where k is from j to N. However, this solution won’t work. It needs $O(n^2)$ space and time, which exceeds the time limit.

There is an $O(n)$ solution, based on the fact that if we start from certain station i, and when we reach j, the gas left is smaller than zero, which means that we can’t reach station j, the stations from i to j-1 can’t be start station. It’s easy to understand. If we can reach station i+1 to j-1 from station i, and can’t reach station j, it means that the cost from station j-1 to j is more than the sum of gas left at station j-1 and the gas station j-1 can provide. Assuming that there is a station from i+1 to j-1 can be a start station, the gas left is zero at start point, which is less or equal to the gas left if we start from station i, so we can’t reach j, which is contradict to our assumption.

So we need to loop twice, because the start station can be the last station, i.e. station N. We maintain a variable indicating the gas left, and a variable startStation indicating the start station now. If the gas left is smaller than zero, we will take the next station as a new start station. If we move to the start station again after setting it, it means that the valid start station exists, otherwise there is no such start station meeting the requirement.

Java code:

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int N = gas.length;
        int gasLeft = 0;
        int startStation = 0;
        for (int i = 0; i < 2 * N; i++) {
            int k = i % N;
            gasLeft = gasLeft + gas[k] - cost[k];
            if (gasLeft < 0) {
                startStation = (i + 1) % N;
                gasLeft = 0;
            }
            else {
                if (startStation == (i + 1) % N)
                    return startStation;
            }
        }
        return -1;
    }
}

public class Solution {

public int canCompleteCircuit(int[] gas, int[] cost) {

int N = gas.length;

int gasLeft = 0;

int startStation = 0;

for (int i = 0; i < 2 * N; i++) {

int k = i % N;

gasLeft = gasLeft + gas[k] - cost[k];

if (gasLeft < 0) {

startStation = (i + 1) % N;

gasLeft = 0;

}

else {

if (startStation == (i + 1) % N)

return startStation;

}

return -1;

}