Problem
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.
Solution
Since the gas tank is unlimited, we always add as much as we can whenever we saw a gas station. At each station, we can calculate if we are able to reach the next one. The check is if the tank will be empty before reaching next station.
gas[0] ->cost[0] -> gas[1] ... gas[i] -> cost[i] -> gas[i+1] ... gas[0]
gas[0] ->cost[0] -> gas[1] ... gas[i] -> cost[i] -> gas[i+1] ... gas[0]
class GasStations {
public static void main(String...args) {
// 3, 5, 6, 2, 9
// 2, 4, 7, 1, 9
// .
//
//
int[] gas = new int[]{3, 5, 6, 2, 9};
int[] cost = new int[]{2, 4, 7, 1, 9};
int start = 2;
canTravel(gas, cost, start); //2 false; 3 true
}
public static int canTravel(int[] gas, int[] cost, int start) {
int N = gas.length;
int sum = 0; //2
for(int i = start; i < N; i++) {
sum += (gas[i] - cost[i]);
if(sum < 0) {
return -1;
}
}
for(int i = 0; i < start; i++) {
sum += (gas[i] - cost[i]);
if(sum < 0) {
return -1;
}
}
return start;
}
}
public static void main(String...args) {
// 3, 5, 6, 2, 9
// 2, 4, 7, 1, 9
// .
//
//
int[] gas = new int[]{3, 5, 6, 2, 9};
int[] cost = new int[]{2, 4, 7, 1, 9};
int start = 2;
canTravel(gas, cost, start); //2 false; 3 true
}
public static int canTravel(int[] gas, int[] cost, int start) {
int N = gas.length;
int sum = 0; //2
for(int i = start; i < N; i++) {
sum += (gas[i] - cost[i]);
if(sum < 0) {
return -1;
}
}
for(int i = 0; i < start; i++) {
sum += (gas[i] - cost[i]);
if(sum < 0) {
return -1;
}
}
return start;
}
}
The time cost is O(N), since we have to iterate all the stations to find the positive answer. The extra space cost is O(1)
