Doubt in solution


How does only traversing till end of array guarantee that i’ll be able to reach the start of the circuit?


As we know that the Total(Gas) >= Total(Cost) for soln. to exist, so while traversing, let us say that the index j gives negative sum difference value i.e.Total(Gas)<Total(Cost) (Total only till index j). Now, we start traversing again from index j+1 making the previous totals (both Total(Gas) and Total(Cost)) as 0, now let us assume that from index j+1 to end of array we don’t find any negative sum difference value. What does that mean?

index --> 0 1 2 3 4…j j+1 j+2 … n-1
values–>(— -ve —) (---- +ve -----)

That means that j+1 index is the soln., because even if we continue taking sum after index n-1 i.e. from 0 we are bound to get +ve value because the overall Total(Gas) >= Total(Cost) exist.
Hence, your answer.

If you want explaination of editorial or (kinda) proof of editorial solution

Thanks. Got the intution behind the solution.