Gas Station - Greedy - Leetcode 134 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
12:15 - Coding Explanation

leetcode 134

#gas #station #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[ZQutui]

Actually, the reason why it works is simple, and it happens because of two factors.
First, if you moved to some value, and your total sum is greater than zero, then it means, that previous values did bring some value to the outcome. For example, we have gas = [2, 3, 0] and cost = [0, 0, 5]. If we take just solely value 3 without 2, it wouldn't be enough to pass the last station, but previous values definitely bring some value to the outcome.
Second, if we know, that there's definitely has to be a solution. Then, we may assume, that it has to be the smallest possible value, as I said before it may bring the most value to the result

[waliddib]

with the current gas prices, we can just return -1 regardless.

[rayahhhmed]

lowkey bro, firstly, i love ur vids as usual but when u started off by confessing that this problem was hard for u too and didnt act like some of those "know all" kind of people,
just shows how down to earth u are and how much we can relate to even someone as good at dsa problems as u.

please keep it up!

[odysy]

A Simple Proof:
1. We are guaranteed that there is one unique solution.
2. The solution must wrap around to the start, and therefore must reach the end of the array at some point.
3. The first index that can reach the end of the array will always result in a higher gas total by the end of the array than any index after it that can reach the end of the array.
4. Therefore, because of conditions 1, 2, and 3, the solution must be the first index that can reach the end of the array.

[RanjuRao]

It was helpful ! Reading these problem statements in leetcode is overwhelming, coming here and looking at the explanations for the same relaxes me honestly :D

[jamesbotwina]

I would add that when we reset the position, we would not want just increment the res, but instead set it to i + 1. We already know that since we are only adding net values that keep the total positive, as soon as we encounter a value that makes the total negative, it must be so large that it none of the previous nets's indexes could can out be a starting value.

[vedantsharma]

The solution would click if you try to apply the pattern as in Kadane's Algorithm.
Try to build a solution from the starting index, once you are certain that it can no longer be an answer, forget everything and consider the next index.

[theSilentPsycho]

Similar to Kadane's Algorithm. In Kadane's we find the ending index of the maximum sum subarray. Here we have to find the starting index of that maximum sum subarray.

[hifan]

Could somebody help explaining this:

At 10:24, why does sum of gas >= sum of cost guarantee a solution?

Thanks!

[pranav]

Its not even greedy, its essentially kadane algo applied on the difference array (gas - cost array).

[prayag]

This might help to understand why the solution works.

Now, we have calculated that the total sum of differences is not negative, i.e Sum(0, N) >= 0.

-> Let's say we found our starting point 'S'.
-> Let us also assume that there was an index 'k' which our solution didn't reach.

We can express the total sum as, Sum(0, N) = Sum(0, k) + Sum(k+1, S-1) + Sum(S, N).

Sum(k+1, S-1) has to be negative, otherwise the starting point would be before S.

Now, As per our assumption we can't reach 'k'.
Therefore, Sum(S, N) + Sum(0, k) < 0.

But, if Sum(S, N) + Sum(0, k) < 0 and Sum(k+1, S-1) < 0, then S(0, N) should also be negative, which we have calculated to be positive.
Therefore, our assumption was wrong.
Hence, there is no point 'k' which our solution cannot reach.

[arpanbanejee]

I will try to explain it in my own way-- please be patient and read it, hope you will get the intuition behind the algorithm.

There are 4 parts to it-

Part 1- sum of gas array>=sum of cost array--->
very intuitive, we should always have enough gas.

Part 2- we are keeping a total+=gas[i]-cost[i] for each i, and whenever it is <0 we are skipping that point and moving forward, making total 0--->
It means we ran out of gas if we started at some point which was <= current pos of i, so now we have to find a new starting position,
which wall be > curr pos of i.
Now think, why will this new start lie ahead of curr pos i, not anywhere before it, you could think, we started from point till as per this algo we try to find start ahead of C, what if we started from B and skipped A instead, well that won't work, You moved from B with some positive value(or 0), or else you would have stopped right at B and made total to 0. So add A improved our chances of having a positive total, so there is no point in looking for the new position start anywhere behind point C.

Part 3- When the total stays +ve, we dn't do anything to the start point, our start pointer points to the first index when our total became positive.
Again this is similar to the above explanation-l
ets suppose we start from X(-ve)--->Y(-ve)--->A(+ve)---->B(+ve)---->C(+ve), where C is the end of the array, our start(which is also the ans) would be A.
Why not B? why not C?
It is because we moved from A to B with some +ve value or atleast 0, whereas if we started from B we would have had only the value of B so earlier point added some value to our total, so its more favorable to help us reach the ans, hence earliest point is always better.

Part 4-- Why we just stop at point C and don t complete the cycle and check.
It is because from Part 1 we would have already identified that if the given set of inputs will have an ans, so if we have reached to Part 3 it means we surely have an ans, and it is mentioned in the question that there is only one valid ans, so we will always choose the most favorable ans-- which is also the fundamental idea of Greedy Algorithims. There is also a mathematical proof for this, that if we got a start point given our total gas >=total cost, we will be able to reach back to that point with just enough gas.

Hope this clears things out!

[willshen]

Although sum(gas) < sum(cost) means there is no solution, it is not obvious that sum(gas) >= sum(cost) means there is a solution.
In fact, I feel you would need math induction to prove that (I know it is valid).

[GoodLuck-dvzu]

There is something common with Kaden's algorithm. Reset the sum when the sum becomes negative.

[riyanshbiswas]

This is by far the best explanation to this problem. I checked a lot of other videos for this problem, but nothing got through my thick skull. You just made it simple and easy and you speak well.
Subbed!

[jayb]

How I see the reasoning for why the first starting index we can reach the end from is the solution:
First, suppose we have an index i that we know we can reach the end from (without our total being < 0). We can ask ourselves this question - can the solution be before this index? Can it be past this index? The answer to both is no. It can't be before the current starting index, because any previous index would have be reset because total < 0 at some point in our algorithm. We already eliminated any index past our current index. So now the solution is either i or past i. Assume it is past i - for some j > i, j is the solution. Then we can start at j and loop back to j. But because i < j, we can go from j to i. And since we can reach the end from i, we can reach j from i. Therefore, we can start at i, go to j, then go back to i, thus making i the solution. The solution is unique so this is a contradiction. The solution cannot be past the first index i that can reach the end. It also can't be before the current index as stated earlier. It is also guaranteed to exist if we are past the initial sum check, so it must be i.

[rle]

Here's a quick proof I attempted regarding why we do not need to loop around!

By implementation of our algorithm, we may assume that upon termination:
1. SUM(gas) >= SUM(costs)
=> SUM(gas) - SUM(costs) >= 0
=> SUM(gas - costs) = SUM(diffs) >=0
=> SUM(diffs) >=0
2.
a) i is the first index from which we were able to reach the end of the list with a non-negative total.
SUM_i_n(diffs) >= 0 iff ABS(SUM_i_n(diffs)) = SUM_i_n(diffs)

b) Equivalently, there is no non-negative total prior to i.
SUM_0_i(diffs) < 0 iff ABS(SUM_0_i(diffs)) = -SUM_0_i(diffs)

We do NOT need to loop around iff the total from i is greater than equal to the total up to i.
That is, we want to prove:
ABS(SUM_i_n(diffs)) >= ABS(SUM_0_i(diffs))

Now the proof.

SUM(diffs) >= 0 [by assumption 1]
<=> SUM_0_i(diffs) + SUM_i_n(diffs) >= 0
<=> SUM_i_n(diffs) >= -SUM_0_i(diffs)
<=> ABS(SUM_i_n(diffs)) >= ABS(SUM_0_i(diffs)) [by assumptions 2.a) and 2.b)]

^so, we have proven that based on the assumptions of our algorithm (our termination condition of i, early return when we precompute diffs), we do not need to loop around.

[shreyakolekar]

There couldn't be an easier explanation to this problem other than the one you showed! Thanks @NeetCode.

[ASMReading_]

I took a similar approach but one I feel is slightly more intuitive. I would consider this a sliding window approach. If anyone's having trouble with this problem, try out this version.

First, create an array called dif, where at each point, dif[i] = gas[i] - cost[i]. What this array tells us is how it affects our gas tank when we're at position i and moving to position i+1. If we see a positive value in dif[i], we know we gain a surplus of gas (because we filled up more than we spent moving forward). If we see a negative value, we know we have a net loss of gas. And if we see a 0, we break even moving forward from i to i+1, and it doesn't impact our gas tank to make this move.

At this point we can start our sliding window approach. Two pointers, start and end, both point to the first element (i.e. start = end = 0). We also keep track of how much gas we have in our tank as we progress on the road trip; we hold this in a variable called tank, initially set to tank=0 because we haven't filled up any gas just yet.

The general idea of the loop is: start marks the start of our road trip, end marks the end. Tank holds the total amount of gas we currently have on a trip from start to end. When we can push end forward, we do; when we can't due to lack of gas, we push start backwards, seeking some extra gas. Let's get more specific with how and when we push forward and back.

Pushing Forward
When exactly can we push the end pointer forward? When tank + dif[end] >= 0. Why? Because this means that all the gas we have in our tank, when also considering the net cost of moving forward by one position (dif[end]), is enough to move us forward without dipping our tank into the negatives. In other words we have enough gas to progress to the next station on this current trip. So in these cases when we're able to extend the trip, we add the value of dif[end] to the tank and then increment end by 1. Then we try to move forward again... until we run out of gas.

Pushing Back
We do this when we run out of gas, i.e. where tank + dif[end] < 0. These are cases where, for example, tank was positive but not high enough to make up for the net loss of moving to the next station. So, in such cases, we seek extra gas by moving the start of our road trip backwards. Every time we move start backwards (i.e. decrement start by 1), we then adjust the value of tank by the new dif[start], because this net gain/loss is now part of our overall road trip and affects our gas tank. It's possible that when we move back one spot, we actually lose gas and the tank dips into the negatives. But we just keep pushing start backwards and updating the value of our tank (adding every new dif[start] to tank), until we reach a value where tank + dif[end] >= 0 and we can begin pushing the end pointer forward again.

End Conditions
Inevitably, because our only two operations are bringing start backwards and pushing end forwards, start will equal end. If we arrive at this condition by pushing end forward, we know the trip was possible, because we only move end forward when possible. In such a case, tank >= 0, because the last step would have ensured tank + dif[end] >= 0, and then set tank += dif[end]. If we arrive at our end condition from moving start backwards, it means we were seeking more gas. If tank >= 0, it means we found the gas we were looking for, and the trip is possible. If tank < 0, it means we never made up for the necessary gas and the trip is impossible. In short, after reaching the point where start = end, we return the index of start if tank >= 0, and -1 if tank < 0.

Why does it work?
I had two concerns with this algorithm, both of which can be dismissed. The first is: when moving start backwards, how do we know it's safe and that we don't accidentally incorporate an impossible path into our route? That is, since we move start backwards and add dif[start] each time, and some of those dif[start] values will be negative, isn't it possible that a section is impossible to pass? This was a little hard to wrap my head around so I may not explain it well, but pretty much it comes down to the fact that we maintain an accurate value in tank for each adjusted start position. When we encounter negative values at dif[start], they push our tank further into the negatives. The only way we can return to pushing end forward is if we find enough positive values at each new dif[start] that we make up for the new loss. For example, if we push start back by 1 and find dif[start] = -50, the only way we'll start pushing end forward again is if we make up for that 50, say by moving start backwards 50 more times and each time finding dif[start] = +1. Positions with a net loss become new blocks until enough surplus gas is found in prior positions to allow us to move past them too.

Second potential issue that can be dismissed: we start by pushing end forward, then as needed pushing start backwards. What happens if the end and start pointers meet at some index k, but the real starting position is somewhere between index 0 and k? We end the code when start and end meet, and start never has a chance to pass end and inspect those earlier indices because it has essentially been moving backwards from the end of the list the whole time. The reason this is not an issue is because we are told that when a solution exists, there is only one unique solution. By the way this algorithm works, end is only pushed forward if it can be and if the resulting tank value is >= 0. A valid solution to this problem is some starting position where, starting with a tank of 0, a circular route can be made. So if we find a path from some start index to the solution index, we have a contradiction: a circuit can be made from the solution index, but since we can reach the solution index from an earlier index with a tank of at least 0 remaining, then that earlier index would be a second solution. Therefore we know end will never pass a valid solution; it will only ever reach it and stop.

Hope this helps!

[jeffreyroh]

Initially, if the sum of cost > sum of gas, we return -1. The difference between gas and cost gives a negative number when we cannot move on to the next index. Using this, we can iterate through the entire list, getting its differences and searching for the index that gives us a positive number. However, the first positive number can be dedcuted into a negative number after it, so we keep track of the positive number and continue to add the difference. Anytime this calculation becomes negative, we need to reset the result pointer and also reset the difference to 0. The index that survives at the end of the full iteration of the array is the point that will let us get through every index, including wrap around.