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.

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

It is easy to come up with a brute force solution: for each gas station, assume it is the starting point, move the car forward (i = (i + 1) % len), add gas[i], substract cost[i], if the remaining gas is never negative and it can go back to the starting point, return the index of the starting point. However this takes O(n^2) time.

Notice that if you can go from i to j, you must have non-negative remaining fuel when reaching j, which means after adding gas at j, you must have greater or equal remaining fuel than gas[j]; so if you cannot go from i to k (i < j < k), then there's no way to start from j to reach k (because if you start from j, it has less or equal gas than passing through j).

The optimized the solution:

• if the total gas is lower than the total cost, there's no solution, return -1.
• assume you start from the gas station start, and at gas station i you do not have enough fuel to reach the next station, set start to i + 1.

The time is reduced to O(n).