Algorithm

LintCode/Gas Station

Problem Summary

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.

Find the index of the starting gas station if you can travel around the circuit once, otherwise return -1.
The solution is guaranteed to be unique.

Solution

Fisrt, let us use diff[i] to denote the amount of gas left if we go to station (i+1) from station i. Apparently, diff[i] = gas[i] - cost[i].

Let sum[i,j] = diff[i] + diff[i+1] + … + diff[j], total = sum[0,N-1].

If there is a feasible solution i, it should satisfy that

sum[i,j] ≥ 0, j = i+1,i+2,…,N-1,0,1,…,i-1.         (1)

Apparently, there is no feasible solution if total is negative. But if total ≥ 0, can we say for sure that there is a solution?

Well, we can prove that

if total ≥ 0, there exits an index i such that (1) holds. (2)

So if total ≥ 0, there must be an answer. Now let us think greedily.
Suppose we begin the journey at j. If we find sum[j,j+k] ≥ 0, but sum[j,j+k+1] < 0, then j is definitely not the answer. Actually, it is unnecessary to consider j+1, j+2, …, j+k+1, either. So we move to consider j’ = j+k+2.
In this way we can find the answer in O(N) time.

Proof of (2)

Let’s assume that

total ≥ 0 but (1) does not hold for any i, 0 ≤ i ≤ N-1.  (3)

The for 0 we have an index p[0] > 0, s.t. sum[0,p[0]] < 0. Since total ≥ 0, we know that p[0] ≠ N-1. Let us suppose p[0] is the first index that satisfies sum[0,i] < 0.

Because of (3), there exits an index p[1] s.t. sum[p[0],p[1]] < 0.
If 0 ≤ p[1] < p[0], we have sum[0,p[0]] + sum[p[0],p[1]] = total + sum[0,p[1]], hence sum[0,p[1]] < 0. So p[0] < p[1] < N-1.

Similiarly, we can find infinite indices p[2],p[3],p[4],… s.t. p[0] < p[1] < p[2] < p[3] < …
But the diff array is finite. With this contradiction, we know that (3) is false, so (2) is true.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    /*
     * @param gas: An array of integers
     * @param cost: An array of integers
     * @return: An integer
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int n = gas.size();
        if (n==0)
        	return -1;
        int total = 0, sum = 0, st = 0;
        for (int i = 0; i < n; ++i)
        {
        	int cur = gas[i] - cost[i];
        	total += cur;
        	if (sum < 0)
        	{
        		sum = cur;
        		st = i;
        	}
        	else
        		sum += cur;
        }
        return total < 0 ? -1 : st;
    }
};