# 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)`

.