There are N gas stations along a circular route, where the amount of gas at station i is
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.
The solution is guaranteed to be unique.
(Java Code on Github at the bottom of the post. )
Q: What is the unknown?
A: The index of the gas station from which we can circle around the route.
Q: What are the data?
A: There are N gas stations. At each station i (i = 0, 1, 2, 3, …, N-1) the amount of gas is gas[i]. The tank is unlimited. To get from station i to i+1, it needs cost[i] amount of gas. We start from an empty gas tank.
Q: Are there any constraints?
A: Yes, the solution is unique and if none satisfies the requirements, return -1.
Q: What do you think is the key point of this problem?
A: That whether we can circle around from a station with index i.
Q: And how would you like to do that?
A: Hmm, we start at index i with L amount of gas in the tank (initially L is zero). If L + gas[i] >= cost[i], that means we can move from index i to i + 1. We repeat this process until we meet the following cases:
- At station k % N (k % N < i), L + gas[k%N] < cost[k%N]. This means that we cannot circle around the route from station i.
- k % N == i. In this case we have circled around the route from station i and we should return i.
Based on this, we can think of a straightforward algorithm. At each station, check if we can circle around the route as stated above.
Q: OK. What is the time complexity of this algorithm?
A: If we are extremely unlucky, we may have to almost circle around the route every time we perform a station check. That takes O(N) time. Since we have to do it for all N stations, I would say this algorithm takes O(N^2) time.
Q: Can we do better than this?
A: Hmm, I don’t think we can improve the station check since we do have to go around all the stations in the circle. But maybe we don’t have to do a station check for each station in the circle. There might be a way to skip some of them based on the result of the previous station checks.
Q: That’s a good thought. Can you think of an example to prove your idea?
A: OK, suppose I’m at station i and I can reach to station j at most where i <= j. That means the left amount of gas L at station j plus gas[j] is less than cost[j]. But then what?
Q: OK, normally we would just go check station i+1 (suppose i + 1 <= j), right? Now can you deduct how far we can get starting from i+1 based on the result of station i?
A: I’m not sure…
Q: When we are at station i + 1 with a fresh start, the amount of gas left in the tank L is zero. We also know that we can go from i to i + 1. So from i to i+1, the amount of gas left in the tank L at station i + 1 must be no less than zero (otherwise we cannot go from i to i + 1). In this case if we can at most get to station j from i, how far do you think we can get to from station i+1?
A: Eh…at most j as well. Ah I get it. If we can go from station i to station j but not circling around the route we should skip all stations from i + 1 to j and only start the next station check at station j + 1.
Q: You got it. So what about the running time of this algorithm?
A: Hmm, in this algorithm each station is checked at most once. So I would say it is an O(N) algorithm.
Q: OK. Go implement this algorithm.
Code on github: