Problems

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