• 29.3%

https://leetcode.com/problems/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.

Note:

The solution is guaranteed to be unique.

Oct 18，2017

My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?

I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

my code:

#### cpp

https://discuss.leetcode.com/topic/1344/share-some-of-my-ideas

Share some of my ideas.

I have thought for a long time and got two ideas:

1. If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.)
2. If the total number of gas is bigger than the total number of cost. There must be a solution.

(Should I prove them?)

Here is my solution based on those ideas:

https://discuss.leetcode.com/topic/5088/my-ac-is-o-1-space-o-n-running-time-solution-does-anybody-have-posted-this-solution

My AC is O(1) space O(n) running time solution. Does anybody have posted this solution?

I have got one solution to this problem. I am not sure whether somebody has already posted this solution.

https://discuss.leetcode.com/topic/39755/proof-of-if-total-gas-is-greater-than-total-cost-there-is-a-solution-c

Proof of “if total gas is greater than total cost, there is a solution”. C++

We prove the following statement.

If sum of all gas[i]-cost[i] is greater than or equal to 0, then there is a start position you can travel the whole circle.
Let i be the index such that the the partial sum

is the smallest, then the start position should be start=i+1 ( start=0 if i=n-1). Consider any other partial sum, for example,

Since gas[0]-cost[0]+gas[1]-cost[1]+…+gas[i]-cost[i] is the smallest, we must have

in order for gas[0]-cost[0]+gas[1]-cost[1]+…+gas[i]-cost[i]+gas[i+1]-cost[i+1] to be greater.
The same reasoning gives that

What about for the partial sums that wraps around?

The last inequality is due to the assumption that the entire sum of gas[k]-cost[k] is greater than or equal to 0.
So we have that all the partial sums

Thus i+1 is the position to start. Coding using this reasoning is as follows:

https://discuss.leetcode.com/topic/8860/fully-commented-o-n-c-solution-enabled-by-a-single-observation-of-mine

Fully-commented O(n) C++ solution enabled by a single observation of mine

https://discuss.leetcode.com/topic/29487/my-one-pass-solution

My one pass solution.

The idea is simple.

1. Whenever the sum is negative, reset it and let the car start from next point.
2. In the mean time, add up all of the left gas to total. If it’s negative finally, return -1 since it’s impossible to finish.
3. If it’s non-negative, return the last point saved in res;

https://discuss.leetcode.com/topic/5088/my-ac-is-o-1-space-o-n-running-time-solution-does-anybody-have-posted-this-solution

6ms, September 20, 2016

#### python

https://discuss.leetcode.com/topic/27760/possibly-the-most-easiest-approach-o-n-one-variable-python

55ms, 32.89%, September 20, 2016

my code的思想类似，不过是移动起点和终点的位置，如果小于0，起点向前移动，如果大于0，则起点向后移动。

my code

#### java

https://discuss.leetcode.com/topic/7247/my-o-n-time-o-1-extra-space-solution

My O(N) time, O(1) extra space solution.

https://discuss.leetcode.com/topic/25289/straightforward-java-linear-solution-with-o-1-space-explanation-and-math-proof

Straightforward Java Linear Solution with O(1) space, explanation and Math proof

The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That’s what the first loop does.

If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station.