Monday, September 15, 2014

Gas station problem

There are some gas stations arranged in a circle. Each of them has some amount of gas. We are also given the distances between all the consecutive stations. Assume that we have a vehicle with very large fuel tank(infinite) and one unit of gas is needed to cover one unit of distance, the problem is to find if we can complete the circuit starting at any gas station.

For example assume that we have the following data

Gas : {3, 1, 2, 5, 4}
Distance: {4, 1, 1, 2, 3}

Station[0] has 3 units of gas, 
Station[1] has 1 unit of gas and so on...

Distance between the stations are interpreted as follows
Station[0] and Station[1] is 4, 
Station[1] and Station[2] is 1, 
Station[4] and Station[0] is 3 , etc...

Let us look at the algorithm for solving this.

We can start at any possible index ( [0, n-1] ), filling all the gas at each station, and move forward if it is possible to reach next station. If we are able to reach the starting position again, We can complete the circle.

What if we are not able reach next station at some point?

For example we start at station i and reached station j and we can not proceed to station (j+1). In a naive approach we start from station (i+1) and see if we can reach station (j+1). This approach works, but it takes O(n2) time.

The catch here is that we can actually start from (j+1) because of the following reason.
If we start at any index between [i+1,j] we can not reach (j+1) since at each step in the previous iteration we had zero or more gas but still we were unable to reach j+1.

For example consider the simple instance
Gas: { 1, 1, 4}
Cost:{ 1, 2, 3} 

If we start from 0 we can reach 1 but we can not reach 2( required: 2 units, present:1 unit). If we start from 1 also, we can not reach 2. So we need not check for this index. We can start from 2 and complete the circle.

So this approach takes O(n) time.

Here is the C++ implementation.