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

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!

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

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 It means we ran out of gas if we started at some point which was 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(totalY(-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

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.

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!

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.

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.

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.

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

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

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.

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.

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

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.

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).

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

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

I submitted NeetCode's solution on (the one on Neetcode's roadmap), and it failed at test 39/40. class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: start, end = len(gas) - 1, 0 total = gas[start] - cost[start] while start >= end: while total < 0 and start >= end: start -= 1 total += gas[start] - cost[start] if start == end: return start total += gas[end] - cost[end] end += 1 return -1

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

Didn't see it mentioned in the comments, but I figured this one out by plotting it on a graph (gas in tank on Y axis, station index on X axis). The ideal starting position is the "absolute minimum" amount of gas in the tank (I let it go negative). The logic here is that if our tank is always "more positive" at all other gas stations relative to the starting point, we can get to the end.

This is a great solution and explanation thank you!

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!

Hey, I think you need to explain a little bit more about why you are setting the start index to i+1 when the total becomes negative. The example you took was failing on every increment but what if you pick the first number and traverse till some 50 entries and then the total becomes negative. Now you need to reset it to 51 and not to the second number. And this is precisely what makes this algorithm O(n) and not O(n^2). The reason why this works is that the reset happens only when the sum of the left entries to that index has become negative. And no matter wherever you start from the left, you will never reach the current index with a positive value, and that is because you have checked at each and every 'i' if it becomes negative or not. Hopefully, this helps someone who has a small confusion about this problem. And hey, Neetcode you are doing God's work! Appreciate it! :)

Nice video. I know that if the sum of gas is lower than the sum of costs then there is no solution. But is it obvious that there must be a solution if the sum of gas is greater than the sum of cost? As in why can't all paths lead to a negative number before being positive, making the tank empty (or negative) before reaching end / origin? This can be proved. But I wanted to know if there was an immediate way to see this. As here it was kind of taken for granted.

My naive solution was O(n^2) and tooks me 3 hours to complete, now I am here in order to understand the neetcode's solutions.

as you said it, it is understandable, but not intuitive at all. Even the brute force took me more time than for a 'usual' problem. I'd classify this a brainteaser. (not sure why it has such a high frequency on leetcode tbh )

Simple explanation for why we can shift the result to i + 1 if we run out of gas: Let's imagine we start at station 0 (which we'll assume has a positive gas-cost difference), but we run out of gas at station 5. If we run out of gas at 5 even WITH station 0 (which has a positive gas value), how are we going to not run out WITHOUT it? Thus, we can conclude that starting at any station in between 0 and 5 (and 5 itself) will also fail to make it through station 5, and shift the starting position to i + 1.

I think a little bit explanation is that as we start from an index and were able to reach the end it means all the right indexes could be the potential solution but as it is told in the problem that we have a unique solution, which implies that the indexes on the right part are just contributing to the solution but not the solution.=>Potentially could nullify the negatives which failed to reach the end of the array.

Very well explained, neetcode is a saviour

To explain simply we are trying to find the starting index of maximum subarray of the difference array which in this case is [-2,-2,-2,3,3] so the starting index of maximum subarray is 3. if we start from 3 our total sum in this array will maximize and since there is a solution we have the maximum subarray so we can conclude that can be the only solution.

here's my interpretation that makes the most sense: so say you have a vector of size 8, and index 5 is where you find your solution as starting point. Sure, starting at index 6 might solve the problem as well, but we are looking at a greedy solution. For example if you start at index 6 with a gas of 7 and cost of 6 , then you have one gas carrying over. But what if you start at index 5? Since we know that at index 5 (the answer) gas[5] >= cost [5], we will get some sort of extra gas carrying over to index 6, we we may get something like gas = 9 and cost = 6 there, which is more gas carrying over to further indexes. This is why the earlier index we start, given that we know the index works, the more gas we'll have down the line and the greedier we can be.

if you see the problem is asking you to find left index of maximum sum subarray so you are use kadane algorithm here

brute force solution that passes all the reasonable tests, except vectors that are 1X10000 def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: n = len(gas) loc_index = {} for i in range(n): if gas[i]>=cost[i]: loc_index[i]= 'Try this!' for key in loc_index: cur_loc = key # i is actual location of cur_loc in the station map, initialization i = cur_loc tank = 0 #This checks to see if we can go through all the stations, while cur_loc< key +n: tank = tank + gas[i] if tank >= cost[i]: tank = tank - cost[i] cur_loc += 1 i = cur_loc % n else: break if i == key %n and gas[i]>=cost[i]: return key print("point",key, ':',i) return -1

The hard part of this problem is proving that that if the total gas is >= total cost, then there must exist a solution. That was not covered in this video. And I wasn't able to follow Leetcode's proof by contradiction so was hoping someone knew how to explain the proof in simpler terms.

Thanks, great video

To me the reason why this works intuitively is because once a sum goes negative we discard it. When our algorithm terminates we hope to have a positive sum for a specific segment (assuming there is a solution). If we know the total sum across all differences is positive, then we know all the negative segments, plus our positive segment, must be positive. Because our solution is unique we need only capture the starting point of this positive segment. And even if our solution were non-unique, by capturing the starting position of the positive sum we maximize the gas we capture.

sum(gas) < sum(cost) is very powerful insight. Then, rest just makes sense. 1. there exists a solution 2. we know which is not a solution. (ie, when sum turns negative). Then whatevers left must be the starting point.

Basically the amount of gas you carry over to the next station. eg. +3, +3, -6. Negative mean you would need 6 gas from the previous stations to proceed

no creater ever confessed that problem is hard ,i started your video and before even watching 10 seconds i figured out the whole solution , but yes this type of problems are more like "either you know or you don't" this was a really weird problem

yo @neetcode another way to look at this. assuming sum(gas) = sum(cost), we know there is one unique soln. let diff = [gas[i] - cost[i] for i in range(len(gas))] sum(diff[0:res]) < 0 by construct of the algorithm sum(diff[res:]) >= 0 by construct we also know that sum(diff[:]) >=0 Thus, sum(diff[res:]) >= abs(sum(diff[0:res])) because the sum of the parts must be >= 0

Great explanation, I implemented my own solution in a different language and got better than 100% of other submissions :)

There is a more intuitive answer in EPI (Elements of Programming Interviews) book, highly encourage to view it. The basic idea is that there is an invariant: "no matter where you start, the lowest gas tank always happen at the same index i". Thus we just need to pick i + 1 for starting point, because we know it will always go up from there. e.g. diff array = gas array - cost array = [-1, 0, -2, 2, 1]. The lowest point of the trip happens at index 2 (val = -2) no matter where you start the trip (try it yourself). Thus the next element (index 2 + 1 = 3) is the (unique) best starting point.

I've watched almost 140 videos of yours, Would love to get an advise from you. How do you come up with such an amazing solutions to the problems? how do you approach the problems, is there any resource that I can use to improve my problem solving skills? Currently I can solve handful (very less) solve medium problems, but most of them, I'm just not able to come up with the solutions! I'm not sure if you're gonna reply to this comment, although trying because it will not only help me but many like me.

The first index i from which we can reach the end is the solution, since the solution can't be before that (we eliminated that) and can't come after it, because any solution j that would follow our i, is reachable by i (we can reach the end so we can reach everything after i) and if j is reachable, then the supposed loop starting from j can also start from i (i => j => loop around => back to i) since there is only one solution, and in this scenario both i and j would be solution, any solution between i and the end of the list can't exist

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.

Simplyyyyy superrrr...... Btw.. can it be done using sliding window also????

" if you fell short, you need to gain more power "

This is hard to come up with. You can use a prefix ideal to solve the problem. It's like finding the biggest gas station in the future road. diff = [0] * len(gas) for k in range(len(gas)): diff[k] = gas[k] - cost[k] if sum(diff) < 0: return -1 max_gas = (0, 0) # gas, k prefix_gas=0 for k in range(len(diff)-1, -1, -1): prefix_gas += diff[k] if prefix_gas > max_gas[0]: max_gas = (prefix_gas ,k) return max_gas[1]

I’m seeing a solution where you go backwards in the array and the index where the backwards sum is greatest is the solution?….assume the sum of cost is >= sum of gas

just brilliant explanation

I dont know why but when I'm stuck and watch the first 2min of a neetcode explanation, I suddenly know how to solve it 😂

The way leetcode explains the problem is very complex. If the problem had a better explanation it would have helped understanding little better. But thankyou for the wonderful solution.

Just had an interview with this question. It took me more than 40 mins to come up with O(n^2) approach T__T

I find all the leetcode problems using greedy solution not related. Really hard to find a common way to solve them.

Great video

Nice explanation bruh

Variation of Kadane's Algorithm

Basically because there is only one solution, you should cumulate as much gas as you can before hitting the very first negative value . So you should start the circle right after the very last negative number

This makes complete sense, your way of explanation makes this intuitive now, THANK YOU!

Let's break down the provided solution step by step: Part 1: Initial check for feasibility The first part of the solution checks whether the total amount of gas available across all stations is sufficient to cover the total cost of the journey. If the sum of available gas is less than the sum of the costs, it implies that there isn't enough fuel to complete the circuit regardless of the starting point. In such cases, the function immediately returns -1, indicating that it's not possible to complete the journey. Part 2: Determining the optimal starting point As we iterate through the stations and update the total gas surplus/deficit, we keep track of the potential starting point (stored in the variable res). Consider the scenario this way: if we run out of fuel at gas station n, then to reach gas station n, all preceding stations must have either added some fuel to our tank or none at all. This implies that if we started at any of these gas stations before n, upon reaching n again, we would encounter a fuel deficit once more. Therefore, it makes more sense to start at the next gas station after n i.e., res = i+1. Part 3: Conclusion and optimization Once we've identified the optimal starting point, we return its index as the solution. Since the problem guarantees a unique solution if it exists, we don't need to continue traversing the circuit once we find the optimal starting point. This optimization ensures that the function terminates efficiently, making it run in linear time complexity (O(n)), as required by the problem constraints. Thanks, a lot for the solution @Neetcode.

how do you prove that as long as you can start, then there must be successful to make a circle?

Thanks a lot for the explanation. I figured it out (eventually), but F ME, this is unintuitive.

To be honest I don't think anybody here really understood 100% why this solution works.

U a God

Could somebody help explaining this: At 10:24, why does sum of gas >= sum of cost guarantee a solution? Thanks!

Yeah, this problem is an interesting bait and switch. It's not regular Greedy, it's Kadane's and a less intuitive use of it at that, mostly in the sense that you really shouldn't overthink why resetting to 0 works.

I just want to suggest to use enumerate rather than range(len).

why did you set res to 0 if you dont use it in your code?

I still don't get why we don't need to go back when we reach the last index...

Thanks

Is it Kadanes Algo?

very good

How will this change if input didn’t say it is guranteed unique solution?

which topic isn't tricky anymore...

what if the diff was [-3,-3,-3,3,2]. the algorithm would return the index of 3 even though the circular root is not possible.

i am sorry but i didnt understand why did i+1 didnt cause an issue at the last index

is this the most optimal solution?

34/40 passed but time exceeded for large inputs :(

Shouldn't start be (i+1)%n? Wheren n is len(gas)

Looks like kadanes algo we pick part with maximum sum

maximum gas path

There really must be a better way to approach Greedy problems in general :(

my first solution: Runtime: 114 ms, faster than 41.03% of JavaScript online submissions for Gas Station. Memory Usage: 39.5 MB, less than 27.45% of JavaScript online submissions for Gas Station. var canCompleteCircuit = function(gas, cost) { const diff = Array(gas.length); for (let i = 0; i=0 && j=0) return i; } } } return -1; };

That was hard

I don't like this problem. It's hard to understand the intuition. For me I had to think about it like this. Assume sum(cost) and sum(gas) are equal. Then for all i, the total gas used, [0 to i-1] + [i to n] == 0. Then 0 to i-1 has some gas deficit required to travel from 0 to i-1. This deficit must be made up for in the leftover gas from i to n because we know that no matter how you split the array in two halves the total is always zero. Thus the first i such that i-n is positive and traversable must contain the leftover gas because [0 to i-1] is exactly equal to [i to n]. If sum(gas) is greater the logic still applies because it's still true that if there's a deficit in 0 to i-1 then i to n must be able to cover it. Thus if you can find some path from i to n that isn't broken it necessarily pays for the left half's travel (0 to i-1).

can i get a reply once

Ok, that didn't really help. Where can I go look for a solid explanation of greedy algorithms?

"This is a problem that is pretty unique" What is unique about this problem?

This is Simple.. you are always starting with postive difference of gas[i]-cost[i] if you get a negative sum , it means there could not be any value which could give you result until of that assumed index and current position. SO we move our possible solution to next index..

My brute force solution: Runtime - 5744 ms Memory usage - 14.3 MB class Solution(object): def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ for i in range(len(gas)): tank_level = 0 # this is our starting gas - start @ station 3 and fill up with 4 units of gas = 0 + 4 = 4 start_idx = j = i tank_level += gas[start_idx] while tank_level >= 0: tank_level -= cost[j] # check if we have enough gas in the tank to get to the next index if tank_level < 0: # we don't so we skip this start_idx and search for another continue j = (j + 1) % len(gas) # ensure we stay in bounds by looping back to index 0 tank_level += gas[j] if start_idx == j: # we found our answer in the clockwise direction return start_idx return -1 # couldn't find an answer

The solution that I found intuitive was to find the maximum subarray of the diff array (need to extend the diff array with itself to account for the cycle) and save the starting index of this maximum subarray. This tells you the optimal starting position, as this is where you can accumulate the most gas. Now you just need to check whether this starting position works by iterating the array once and checking if the tank ever goes empty. This solution is also O(n), though a bit less efficient than the proposed solution in the video. Maybe this helps someone. def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: diff = [g - c for g,c in zip(gas, cost)] if sum(diff) < 0: return -1 doubled = diff + diff # double the array because we have to do a circuit best_start = self.maxSubArrayStart(doubled) % len(diff) # convert back to original index credit = 0 index = best_start for i in range(len(diff) + 1): credit += doubled[index] if credit < 0: return -1 index += 1 return best_start def maxSubArrayStart(self, vals): res = -math.inf cur_max = -math.inf l, index = 0, 0 for i in range(len(vals)): if vals[i] > cur_max + vals[i]: l = i cur_max = max(cur_max + vals[i], vals[i]) if cur_max > res: res = cur_max index = l return index

For People like me below solution is better readable def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(gas) < sum(cost): return -1 total = 0 for index in range(len(gas)): total = gas[index] - cost[index] if total < 0: continue for inner_i in range(index+1, len(gas)): total = total + gas[inner_i] - cost[inner_i] if total < 0: break else: return index