Greedy
One pass with a reset
Two separate facts, each cheap: whether an answer exists at all, and where it must be.
Key idea
A circular route with gains and costs
You travel around a circle of stops. Each stop gives you something and each leg costs something. Find a starting stop from which you can complete the loop without ever running out, or report that none exists.
Trying each start and simulating is quadratic. The greedy version answers it in one pass, and it is built from two independent observations rather than one clever rule.
Why it works
Does any answer exist?
Sum the gains and sum the costs over the whole circle. If the total gain is less than the total cost, no start can work, because completing the loop from anywhere consumes exactly that difference.
If the total gain is at least the total cost, a valid start is guaranteed to exist. That is a genuine theorem rather than an intuition, and proving it is what the second observation does.
Why it works
Where must it be?
Walk once, carrying the running balance. Whenever the balance goes negative, no stop from the current candidate start up to here can work, because starting later within that stretch only removes non-negative prefixes and cannot help.
So discard all of them at once: set the candidate start to the next stop and reset the balance. One pass, and the candidate that survives to the end is the answer.
That is the exchange argument in a different shape. Rather than showing the chosen option is safe, it shows a whole block of options is provably unsafe and can be discarded together.
The running balance is the thing to watch. Below it is printed per stop, along with the moment a whole block of candidates gets thrown away.
Tip
Why the surviving candidate needs no verification
The total check guarantees an answer exists. The reset rule guarantees every discarded stop is invalid. Only one candidate survives the pass, so it must be the answer, and simulating it again would be wasted work.
That two-part structure is worth recognizing. A cheap global check establishes existence, and a local rule eliminates everything else. Neither half alone is a solution.
Gotcha
Reset the balance, do not carry the deficit
When the candidate start moves, the balance restarts at zero rather than keeping the negative amount. The deficit belonged to a stretch that has been abandoned entirely.
Carrying it forward makes later stretches look worse than they are and can reject a valid start. The running total and the total-over-the-circle are two different quantities and only one of them resets.
Cost
Cost
Two passes, or one if the totals are accumulated inside the same loop, so O(n) time and O(1) space against the quadratic simulation.
Combining the two passes is easy and slightly obscures the structure. Writing them separately first, then merging if asked, keeps the two observations visible.
Why can the whole stretch be discarded?
The running balance goes negative at stop k, having started the current attempt at stop s. Why can every stop from s to k be ruled out at once?
Gas Station
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.