Gas station

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.

(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:

  1. 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.
  2. 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:

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s