Lintcode: 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 costscost[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.

Have you met this question in a real interview? 

Yes

Example

Given 4 gas stations with gas[i]=[1,1,3,1], and the cost[i]=[2,2,1,1]. The starting gas station's index is 2.

Note

The solution is guaranteed to be unique.

Challenge

O(n) time and O(1) extra space

Tags Expand 

Greedy

Initial violent solution:
Use one loop to let the car start off at each station, and use another loop to test whether this car is able to travel around the circle.
Time: O(n^2)
Space: O(1)

class Solution {
public:
    /**
     * @param gas: a vector of integers
     * @param cost: a vector of integers
     * @return: an integer 
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // write your code here
        int N = gas.size();
        for(int i = 0; i < N; i++){
            int mygas = 0;
            for(int j = i; j < i + N; j++){
                int cur = j % N;
                mygas += gas[cur];
                if(mygas >= cost[cur]) mygas = mygas - cost[cur];
                else break;
                if(j == i + N - 1) return i;
            }
        }
        return -1;
    }
};

Greedy Solution:

1)The key is that if gas sum(0 ~ i) is less than cost[i], then we just need to let car start off after i.

My initial greedy solution thought:
I understand the key point above.
Refer to other solutions online, they just iterate the loop once, even don't prove that when car start off at the last gas station, whether it is able to drive one circle. Because they all have an assumption that

2)if sum(gas[i] - cost[i]) >= 0, there must be an solution.
But why?...
Here is a great proof.
http://bookshadow.com/weblog/2015/08/06/leetcode-gas-station/
In version 1, I just use property 1) so I evaluate the existence when car start at any element,
Time: O(2n)
Space: O(1)
In version 2, I use both 1) and 2>. we know that if sum gas >= sum cost, there must be a solution. So we just need to get the last station where car cannot proceed.
Time: O(n)
Space: O(1)

Version 1:

class Solution {
public:
    /**
     * @param gas: a vector of integers
     * @param cost: a vector of integers
     * @return: an integer 
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // write your code here
        int N = gas.size();
        for(int i = 0; i < N; i++){
            int mygas = 0;
            int count = 0;
            while(true){
                count++;
                int cur = i % N;
                mygas += gas[cur];
                if(mygas >= cost[cur]) {
                    mygas = mygas - cost[cur];
                    i++;
                }else{
                    //i++;
                    break;
                }
                if(count == N) return i%N;
            }
        }
        return -1;
    }
};

Version 2:

class Solution {
public:
    /**
     * @param gas: a vector of integers
     * @param cost: a vector of integers
     * @return: an integer 
     */
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // write your code here
        int sum = 0;
        int tempsum = 0;
        int j = -1;
        for(int i = 0; i < gas.size(); i++){
            sum = sum + gas[i] - cost[i];
            tempsum = tempsum + gas[i] - cost[i];
            if(tempsum < 0){
                j = i;
                tempsum = 0;
            }
        }
        if(sum < 0) return -1;
        return j + 1;
    }
};

DP solution: not a good one, try later
O(n^2)

Reference:
动态规划求解最大字段和及其变种问题



Lintcode second:

O(n^2) solution:

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

class Solution { public: /** * @param gas: a vector of integers * @param cost: a vector of integers * @return: an integer */ //3:30 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { // write your code here int sum_gas = 0; int sum_cost = 0; for(int i = 0; i < gas.size(); i++){ int sum_gas = 0; int sum_cost = 0; for(int j = i; j < i + gas.size();j++){ j = j % gas.size(); sum_gas += gas[j]; sum_cost += cost[j]; if(sum_gas < sum_cost) break; if(j == (i + gas.size() - 1) % gas.size()) return i; } } return -1; } };