Gas Station - Greedy - Leetcode 134 - Python

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

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

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!

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 A------>B(total till +ve)------->C(total<0), 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 A--------> 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!

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

I too had difficulty understanding the solution in leetcode. Felt good seeing you mention the same. Great videos, NeetCode...You are my first youtube video for problems i have trouble understanding. Much appreciated!!

This is the first actually challenging leetcode medium I've been able to figure out the efficient solution for perfectly myself in less than 30 minutes. I've done 50 of the Neetcode 150. Thank you.

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!

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.

Great vid, thanks! You said in the beginning that there are not many problems like that in leetcode, but this seems to be very similar to finding the largest subarray.

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.

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

I scratched my head too long for this on leetcode. Good explanation. Thank you for this.

Amazing explanation as always.. I totally love your videos and how simple you make them to understand them.

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.

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.

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.

Superb explanation, i was stuck with the brute force approach.

It seems like the opposite of greed(y) because we keep the first solution (the first starting point) we find. But it is actually greedy because we only keep it as long as it's useful for us (meaning we still have gas). So, yes that's tricky for me.

This is a great solution and explanation thank you!