C++ Coding Exercise – 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.
The solution is guaranteed to be unique.

Submit your solution at: https://leetcode.com/problems/gas-station/

It is obvious that there isn’t any solution (should return -1) if the sum of gas[] is smaller than sum of cost[] array. We try and record the start position. If at any time, we find that the tank + gas[i] – cost (current fuel amount) is less than zero, we find an impossible route. In this case, we set the start position at next station, and re-initialize the fuel amount of the car to zero.

There is an important fact that if we run out the gas at station i then starting anywhere from 0 to i – 1 would be futile. That is due to: the accumulated sum from station 0 to station i-1 is positive, i.e. Removing a positive number will not make the sum bigger at station i.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int start = 0;
        int total = 0;
        int tank = 0;
        for (int i = 0; i < n; i ++) {
            int dif =  gas[i] - cost[i];
            tank += dif;       // extra fuel in tank
            total += dif;     
            if (tank < 0) {
                start = i + 1; // should start from next
                tank = 0;      // empty the tank
            }
        }
        // if total cost is larger than total gas, then impossible
        return total < 0 ? -1 : start;
    }
};

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int start = 0;
        int total = 0;
        int tank = 0;
        for (int i = 0; i < n; i ++) {
            int dif =  gas[i] - cost[i];
            tank += dif;       // extra fuel in tank
            total += dif;     
            if (tank < 0) {
                start = i + 1; // should start from next
                tank = 0;      // empty the tank
            }
        }
        // if total cost is larger than total gas, then impossible
        return total < 0 ? -1 : start;
    }
};

The requirements for a solution are: We finish iterating the array and we have the last-recorded start position, and the is bigger than zero.

One pass, O(n) complexity.

–EOF (The Ultimate Computing & Technology Blog) —