Another approach

Tags: #<Tag:0x00007f1828e45c90>


There is a simple approach to solve this question.
let Start is the starting gas station.
For every index i in array we are given fuel gas[i] and travel cost is taken from us as cost[i], ultimately we have gain = gas[i]-cost[i] at every index.

For any index i, if the previous cumulative sum of all gain from start to i, is less than 0 then that cumulative gain is no benefit for current index i and our current index become the solution, i.e we want our fuel to increase due to effect of previous gas stations not decrease it with negative gain.

In simple if at any index cumulative sum of gain from start is less than 0 than start is not the solution, move start to i and gain to fuel[i]-cost[i] .

Terminating Condition: If cumulative gain >= zero andi approached start from a decreasing index, start is the solution.

For no solution to exist, if cumulative gain is less than zero and i approached start from a decreasing index, there is no solution.

TC: O(n)