Leetcode and Lintcode

Gas Station

Problem:

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.

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

Solution:

Use a ‘total’ variable to record the total amount of gas left through the circus.
Use a ‘sum’ variable to record the current gas left in the tank.
Use a pointer to record the starting label.
Once the there is no gass left in the car before next gas station available, set the label next gas station as the new starting gas station.

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
/*************************************************************************
	> File Name: GasStation.java
	> Author: Yao Zhang 
	> Mail: psyyz10@163.com 
	> Created Time: Sun 15 Nov 19:33:24 2015
 ************************************************************************/

public class GasStation{
    public int canCompleteCircuit(int[] gas, int[] cost){
        int sum = 0;
        int total = 0;
        int label = 0;

        for (int i = 0; i < gas.length; i++){
            total += gas[i];
            sum += gas[i];

            total -= cost[i];
            sum -= cost[i];

            if (sum < 0){
                sum = 0;
                label = i + 1;
            }
        }

        return total >= 0 ? label : -1;
    }
}