Gas Station BS

Here’s the problem. Gas Station - LeetCode
After transforming diff = gas[i] - cost[i], basically you are finding a start where you could go all around the diff without dipping into negative.
First Intuition: if sum(gas) > sum(cost), we ALWAYS have a solution.
And since solution is ensured to be unique, we just need to figure out how.
Turns out there’s a trick (that I myself dont understand very well, but basically)

1. If you start at s and then you get stuck at j, then there are no other start s+i that’s between s and j that would be valid, since the in-between index cannot have as much gas, this mean when stuck we reset completely to the next start atj+1
2. This is the second intuition: it is that given that we have a solution, the first index that can accumulate to the end without getting stuck is the solution.

Why? well it’s reasoned (by GPT) that the last non-stucking index would also be the first index right after the biggest dips, meaning this would be the biggest accumulation point and would payback for all the previous dips. This also means that when we find this index, we don’t have to go full circle wrap around and check for validity, this is ensured.

Want an example? here goes:

gas = [1,2,3,4,5] 
cost = [3,4,5,1,2]
diff = [-2,-2,-2, 3, 3]

The accumulated gas dips 3 times and get minimal at index 2, and then later index 3 is the one that we can scan to the end, making it the solution.
This would be the same for any case, say i move the diff index around diff = [-2,-2, 3, -2, 3], It can easily be seen that the new biggest dip is 1, and the good index is 2.
If i move it again diff = [-2, 3, -2, -2, 3], then the correct one is the last index, since this is the one after the two dips (-2, -2)

Get it? dont get it? Me too, but we digress. 😆