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
Yes I got it! 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. Hope this clears things out!
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!
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 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!
I had trouble understanding part2: I finally made peace thinking this way. assume you were coming from A-->B-->C with certain force, but you were not able to tackle the obstacle at C because C was big enough, even with all previous value combined. Hence if you are starting from B, you essentially reduce the force because you are selecting a smaller chain than the previous chain.
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!!
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.
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 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 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.
Thanks, that's the actual proof. If Sum(0, k) + Sum(k+1, S-1) + Sum(S, N) is positive, and the second term Sum(k+1, S-1) is negative, then the sum of the first and third Sum(0, k) + Sum(S, N) must be positive. QED. In other words, A+B+C positive and B negative implies A+C positive. It's intuitive that B is negative, but IMO it's not entirely trivial to prove it. See the comment by @purnawirmanhuang5145 for an alternative algorithm.
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.
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!
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!
My version of the code in Python. Note I didn't make a separate dif array, just updated the gas array to keep it to O(1) additional space. for i in range(len(gas)): gas[i] -= cost[i] start = 0 end = 0 tank = 0 # initial push of end as far as possible while end < len(gas) and tank + gas[end] >= 0: tank += gas[end] end += 1 # if full circle completed if end == len(gas): return 0 # if not returned, we need more gas to proceed # alternate moving start and end until they meet start = len(gas) - 1 tank += gas[start] while start != end: # case where more gas is needed if tank + gas[end] < 0: start -= 1 tank += gas[start] # case where can proceed else: tank += gas[end] end += 1 if tank >= 0: return start return -1
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.
Ah this made it click for me. Basically at our first point where we can reach the end with non-zero gas at every stop, we know for sure there is no solution before this point. If there was another solution after this point, our current index can only be better, so there must be two solutions which is not possible. Since we know there must be a solution, assuming we've already checked sum(gas) > sum(gas), and we know there can be no answer preceding the index and no answer after the index, the first index must be the solution. I think the key here is the unique solution constraint.
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
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! :)
To illustrate the above point ! Eg: If our difference array is 10 10 -35 4 8 We start from index 0 Our total will be negative at index 2 In that case we start from index 3 and not from index 1 , thats what the comment tries to say because any index picked between 0 and 2 as a starting point will give a negative value anyways so we begin from (2+1) th index as starting point and thats how its linear tc approach.
This is because if sum became negative at a point you would have considered that as the breaking point already. When you reach a point where sum became negative you again start from the breaking point +1 as new index.
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.
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
I see it in this way: Find the starting index of the maximum sum circular subarray, considering each element as gas[i] - cost[i], similar to the "Maximum Subarray Sum" problem; a valid start exists if total gas >= total cost.
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.
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.
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.
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 reason that circular check is not needed is that since the total sum is positive, the sum from the last negative point to the end is guaranteed to offset all previous negative sums and still have some surplus.
This is easier to understand if you reframe it as finding the starting index of the maximum subarray of the differences: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: if sum(cost) > sum(gas): return -1 # calculate diff diff = [] sum_ = 0 for i in range(len(gas)): diff.append(gas[i] - cost[i]) sum_ += diff[i] # kadanes algorithm maxSum = float("-inf") curSum = 0 index = 0 for i, n in enumerate(diff): if curSum < 0: curSum = 0 index = i curSum += n maxSum = max(maxSum, curSum) return -1 if maxSum < abs(sum_ - maxSum) else index
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.
its basically like saying that since 1> the question says there is a solution, unique 2> the leftmost non zero candidate element is the best candidate for being the solution, as the elements to its right are adding it up further so we choose it as our 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.
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.
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).
Let me give you a brief idea, if your haven't done any math induction, you might not be able to get it. First, we find the diff between the gas and cost, which is also a circle, we call it D(diff). The problem becomes: There is a circle called as D , if sum(D) >= 0, we can always find a starting point on D, such that when doing an accumulation sum, the sum would always >= 0. First Step: If there are continuous negative numbers or positive numbers, we sum them up. For example,[1,2,3,-2,1,-3,-2] -> [6,-2,1,-5] we can do this because starting from 1 would be surely better than starting form 2 or 3. and we are not going to start the solution from any negative number. we call this new circle DC (compressed diff). Now D become [+-+-+-+-...+-], N pairs of positive and negative number. You might need to rotate the circle to make sure the first element is positive. Example 1 in LC: Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Diff=[-2,-2,-2,3,3] CD=[-6,6] -> [6,-6] (by rotation) Solution: starting from CD[0], which is gas[3] Going to do induction on number of pairs in CD, call it N. Base case: K = 1, we start solution from the only positive element. It is for sure we have a solution. Induction: assume that when K =N -1the statement is true, show K = N is also true. As sum(CD) > 0, we can find at least one pair of nums [a, b], such that a +b >=0, a >0 (otherwise, if every pair has sum 0, this new circle is an example of K= N-1, and therefore it must have a solution. We call the starting point of the solution s, s would be one of the positive number in CD*. There are two possibilities: 1: s is not d, we are going to show s is also solution for CD : we have: CD*: [+-,...,s-,+-,.....+-,d-,+-,......+-] where starting from s is a solution of D*. because s is a solution, we know sum(s,d-1)>=0 . as a >0, sum(s,a) >0, as a+b >=0, sum(s,b) >=0, as c >0, sum(s,c) >0. After c, there is no diff between D and D*, so all accumulated sum >= 0. e is a solution for CD. 2: e is d , going to show "a" would be the solution for CD as a>0, a+b >=0, a+b+c >=0, we know it is not stopped at abc, then after c, there is no diff between CD and CD*. As d is solution for CD*, then "a" would be a solution for CD, (because sum(a,b,c) is d)
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 )
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 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.
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
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.
I could explain the reason on why it works with plain english without any equation. Everyone has doubt of loop We have two key points: 1. There is only one answer. 2. There will be a answer (We confirmed whether the answer exist in first if check) With these two, thing the negation case. We have to confirm whether current index is answer or not. Everytime we cross a index it means the index is not the answer if ever the total(surplus) goes less than zero, so if we don't get shortage while starting from an index, then we could confirm it is the solution based on above two key points.
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
I’d did it a slightly different way. Looped through the lists adding and subtracting to the tank. then took the index at the minimum tank. Just as fast. Needed an extra variable.
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.
For anyone that sees this: if we guarantee that (sum of gas) - (sum of costs) is positive, if a "path leads to a negative number" like he says, we know the path must eventually make up for that net negative fuel, as guaranteed by our net positive gas sum. So we simply start at whatever station makes up for that net negative run. Imagine that we have the net positive gas sum. Now imagine that for 100 stations in a row, we get 0 gas and it costs 1 gas to travel. We're at -100. But by our sum property, this deficit must be made up somewhere. Then station 101 will give us 100 gas, and we should start the cycle at station 101 (or some other net-positive run that enables us to start there).
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.
Proof by contradiction on why we don't need to circle back: First, you know at least one solution exists. Assume you started checking index i as a potential starting position, which means the solution can't be to the left (among indices 0 to i-1) because the gas dipped below zero at some point when you started from them. -> the solution should be either the current index i, or to the right (i+1 to n). Starting from index i, you go until the end of the array, calculating gas and cost difference, and the gas in your tank never dips below zero. Now this means that starting at index i is a valid solution to the problem, why? Because we already know there is a solution somewhere and it is somewhere along i to n. From i, you can apparently reach all of these with >= 0 gas in your tank. If you can reach the solution with a non-negative gas, that means you can go forward from that point and make a full circle. But if the solution is not i itself, that means there has to be two solutions, because you can go from i to that solution i+k and then come back to i. Since the constraints tell us that there is only one solution, that means the i must be the solution. Proof why we can skip the things between the starting point and the current index when the gas in the tank dips below zero: For an index to be a starting point, you should be able to start from that index (with a 0 - empty tank, but having extra gas won't hurt) and make a full circle. The fact that you went over them at some point means that your tank was non-negative as you crossed it, but still you ran out of gas later on. That means those indices can't be valid starting points so you can safely skip over them. This is the most important part and what makes the algorithm O(n).
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]
Solution for Java folks - 💪 class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int totalGas = 0; int totalCost = 0; for(int i=0; i
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.
Excellent, thank you ! The diff array works like a conservative field. The partial sums work like a potential. We start at the minimum of the potential. en.wikipedia.org/wiki/Conservative_vector_field n = len(gas) s = 0 min_val = 1000000 min_ind = None for i in range(n): s += gas[i] - cost[i] if s = 0 else -1
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
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
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.
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.
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
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.
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; };
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.
it's useful to think in terms of the diff array. The condition that sum of gas >= sum of cost means that the sum of diff array >=0. This means that, there is at least one starting point from which you can iterate through the rest of the array (to be more precise, if starting point is i, you go over i, i+1, i+2 ,..., n , 0 , 1 , ... i-1, where n is the length of the array) while keeping the running sum >=0 (i.e. not running out of gas). In the example considered [-2, -2, -2, 3, 3], index 3 is the starting point, since you can go around it until index 2 and the sum of the array will always be >=0 (which means trip is complete). But of course, the condition alone does NOT tell you where the starting point is, that is done in a greedy fashion as described in the video
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { int gasSum = Arrays.stream(gas).sum(); int costSum = Arrays.stream(cost).sum(); if(gasSum < costSum){ return -1; } int total =0, start = 0; for(int i=0;i
It's a tricky problem. I feel really surprised to find that there are quite a lot of companies using it to test job candidates. Did you get any comments or feedbacks from the interviewer on your answer to this question?
no worries man. The brute force is actually a bit tricky as well since you have to figure out how to do a "cycle for loop". And it's almost impossible to think of this greedy method unless you already studied this kind of question before.
var canCompleteCircuit = function(gas, cost) { let totalTank = 0; // Total balance of gas let currTank = 0; // Current balance of gas let startStation = 0; // Potential starting station for (let i = 0; i < gas.length; i++) { let diff = gas[i] - cost[i]; totalTank += diff; // Add to total gas balance currTank += diff; // Add to current gas balance // If current balance goes negative, reset the start station if (currTank < 0) { startStation = i + 1; // Try starting from the next station currTank = 0; // Reset current gas balance } } // If total gas is negative, it's impossible to complete the circuit return totalTank >= 0 ? startStation : -1; };
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..
Can you think of the gas and cost array as well? I feel there might not be a pair of gas and cost array where sum(gas) >= sum(cost) and also the condition of only one unique solution
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
Interesting solution. One note though I don't think we actually need the for loop in canCompleteCircuit. If we dont return on the first if check we're guaranteed a solution
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
Yes, nicely explained!
could not understand the last line... : (
Yes I got it! 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.
Hope this clears things out!
is it somewhat similar to Kadane's Algorithm?
@@arpanbanejee5143 This is great! Thanks!
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.
⛽ 😭
Lol
😂
😂
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 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!
Best explanation found so far.
Thank you!!
The key is "t 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. "
Thank you so much!! Best explanation ever.
I had trouble understanding part2:
I finally made peace thinking this way.
assume you were coming from A-->B-->C with certain force, but you were not able to tackle the obstacle at C because C was big enough, even with all previous value combined. Hence if you are starting from B, you essentially reduce the force because you are selecting a smaller chain than the previous chain.
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!!
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.
But that would be O(n^2) right
@@mostinho7 no, that's the point of "forgetting everything in between" and consider the next index, if you do that we wont be doing repetitive work
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 comment made the solution click for me thank you
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 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.
Thanks for the explanation.
Beautiful explanation
Thanks, that's the actual proof.
If Sum(0, k) + Sum(k+1, S-1) + Sum(S, N) is positive,
and the second term Sum(k+1, S-1) is negative,
then the sum of the first and third Sum(0, k) + Sum(S, N) must be positive. QED.
In other words, A+B+C positive and B negative implies A+C positive.
It's intuitive that B is negative, but IMO it's not entirely trivial to prove it.
See the comment by @purnawirmanhuang5145 for an alternative algorithm.
@@davidespinosa1910 omg this this amazing thank you
There couldn't be an easier explanation to this problem other than the one you showed! Thanks @NeetCode.
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.
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!
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!
My version of the code in Python. Note I didn't make a separate dif array, just updated the gas array to keep it to O(1) additional space.
for i in range(len(gas)):
gas[i] -= cost[i]
start = 0
end = 0
tank = 0
# initial push of end as far as possible
while end < len(gas) and tank + gas[end] >= 0:
tank += gas[end]
end += 1
# if full circle completed
if end == len(gas):
return 0
# if not returned, we need more gas to proceed
# alternate moving start and end until they meet
start = len(gas) - 1
tank += gas[start]
while start != end:
# case where more gas is needed
if tank + gas[end] < 0:
start -= 1
tank += gas[start]
# case where can proceed
else:
tank += gas[end]
end += 1
if tank >= 0:
return start
return -1
Interesting alternative, thanks for sharing.
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.
Ah this made it click for me. Basically at our first point where we can reach the end with non-zero gas at every stop, we know for sure there is no solution before this point. If there was another solution after this point, our current index can only be better, so there must be two solutions which is not possible. Since we know there must be a solution, assuming we've already checked sum(gas) > sum(gas), and we know there can be no answer preceding the index and no answer after the index, the first index must be the solution. I think the key here is the unique solution constraint.
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
good way to think abt it
There is something common with Kaden's algorithm. Reset the sum when the sum becomes negative.
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! :)
To illustrate the above point !
Eg:
If our difference array is
10 10 -35 4 8
We start from index 0
Our total will be negative at index 2
In that case we start from index 3 and not from index 1 , thats what the comment tries to say because any index picked between 0 and 2 as a starting point will give a negative value anyways so we begin from (2+1) th index as starting point and thats how its linear tc approach.
This is because if sum became negative at a point you would have considered that as the breaking point already.
When you reach a point where sum became negative you again start from the breaking point +1 as new index.
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.
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).
I see it in this way: Find the starting index of the maximum sum circular subarray, considering each element as gas[i] - cost[i], similar to the "Maximum Subarray Sum" problem; a valid start exists if total gas >= total cost.
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.
I scratched my head too long for this on leetcode.
Good explanation. Thank you for this.
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.
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.
this is very intuitive, thx!
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 reason that circular check is not needed is that since the total sum is positive, the sum from the last negative point to the end is guaranteed to offset all previous negative sums and still have some surplus.
This is easier to understand if you reframe it as finding the starting index of the maximum subarray of the differences:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(cost) > sum(gas):
return -1
# calculate diff
diff = []
sum_ = 0
for i in range(len(gas)):
diff.append(gas[i] - cost[i])
sum_ += diff[i]
# kadanes algorithm
maxSum = float("-inf")
curSum = 0
index = 0
for i, n in enumerate(diff):
if curSum < 0:
curSum = 0
index = i
curSum += n
maxSum = max(maxSum, curSum)
return -1 if maxSum < abs(sum_ - maxSum) else index
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.
thanks
its basically like saying that since
1> the question says there is a solution, unique
2> the leftmost non zero candidate element is the best candidate for being the solution, as the elements to its right are adding it up further so we choose it as our 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.
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.
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).
I challenge you... Please prove it
Let me give you a brief idea, if your haven't done any math induction, you might not be able to get it.
First, we find the diff between the gas and cost, which is also a circle, we call it D(diff).
The problem becomes: There is a circle called as D , if sum(D) >= 0, we can always find a starting point on D, such that when doing an accumulation sum, the sum would always >= 0.
First Step:
If there are continuous negative numbers or positive numbers, we sum them up.
For example,[1,2,3,-2,1,-3,-2] -> [6,-2,1,-5] we can do this because starting from 1 would be surely better than starting form 2 or 3. and we are not going to start the solution from any negative number. we call this new circle DC (compressed diff).
Now D become [+-+-+-+-...+-], N pairs of positive and negative number. You might need to rotate the circle to make sure the first element is positive.
Example 1 in LC:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Diff=[-2,-2,-2,3,3]
CD=[-6,6] -> [6,-6] (by rotation)
Solution: starting from CD[0], which is gas[3]
Going to do induction on number of pairs in CD, call it N.
Base case: K = 1, we start solution from the only positive element. It is for sure we have a solution.
Induction: assume that when K =N -1the statement is true, show K = N is also true.
As sum(CD) > 0, we can find at least one pair of nums [a, b], such that a +b >=0, a >0 (otherwise, if every pair has sum 0, this new circle is an example of K= N-1, and therefore it must have a solution. We call the starting point of the solution s, s would be one of the positive number in CD*.
There are two possibilities:
1: s is not d, we are going to show s is also solution for CD :
we have:
CD*: [+-,...,s-,+-,.....+-,d-,+-,......+-] where starting from s is a solution of D*.
because s is a solution, we know sum(s,d-1)>=0 .
as a >0, sum(s,a) >0,
as a+b >=0, sum(s,b) >=0,
as c >0, sum(s,c) >0.
After c, there is no diff between D and D*, so all accumulated sum >= 0. e is a solution for CD.
2: e is d , going to show "a" would be the solution for CD
as a>0, a+b >=0, a+b+c >=0, we know it is not stopped at abc, then after c, there is no diff between CD and CD*. As d is solution for CD*, then "a" would be a solution for CD, (because sum(a,b,c) is d)
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 )
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 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.
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
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.
I could explain the reason on why it works with plain english without any equation.
Everyone has doubt of loop
We have two key points:
1. There is only one answer.
2. There will be a answer (We confirmed whether the answer exist in first if check)
With these two, thing the negation case. We have to confirm whether current index is answer or not. Everytime we cross a index it means the index is not the answer if ever the total(surplus) goes less than zero, so if we don't get shortage while starting from an index, then we could confirm it is the solution based on above two key points.
" if you fell short, you need to gain more power "
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
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.
Amazing explanation as always.. I totally love your videos and how simple you make them to understand them.
I’d did it a slightly different way. Looped through the lists adding and subtracting to the tank. then took the index at the minimum tank. Just as fast. Needed an extra variable.
I had to return res%len(gas) becase i tool total gas
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.
For anyone that sees this: if we guarantee that (sum of gas) - (sum of costs) is positive, if a "path leads to a negative number" like he says, we know the path must eventually make up for that net negative fuel, as guaranteed by our net positive gas sum. So we simply start at whatever station makes up for that net negative run.
Imagine that we have the net positive gas sum. Now imagine that for 100 stations in a row, we get 0 gas and it costs 1 gas to travel. We're at -100. But by our sum property, this deficit must be made up somewhere. Then station 101 will give us 100 gas, and we should start the cycle at station 101 (or some other net-positive run that enables us to start there).
Very well explained, neetcode is a saviour
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.
Proof by contradiction on why we don't need to circle back:
First, you know at least one solution exists. Assume you started checking index i as a potential starting position, which means the solution can't be to the left (among indices 0 to i-1) because the gas dipped below zero at some point when you started from them. -> the solution should be either the current index i, or to the right (i+1 to n).
Starting from index i, you go until the end of the array, calculating gas and cost difference, and the gas in your tank never dips below zero. Now this means that starting at index i is a valid solution to the problem, why? Because we already know there is a solution somewhere and it is somewhere along i to n. From i, you can apparently reach all of these with >= 0 gas in your tank. If you can reach the solution with a non-negative gas, that means you can go forward from that point and make a full circle. But if the solution is not i itself, that means there has to be two solutions, because you can go from i to that solution i+k and then come back to i. Since the constraints tell us that there is only one solution, that means the i must be the solution.
Proof why we can skip the things between the starting point and the current index when the gas in the tank dips below zero:
For an index to be a starting point, you should be able to start from that index (with a 0 - empty tank, but having extra gas won't hurt) and make a full circle. The fact that you went over them at some point means that your tank was non-negative as you crossed it, but still you ran out of gas later on. That means those indices can't be valid starting points so you can safely skip over them. This is the most important part and what makes the algorithm O(n).
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]
Solution for Java folks - 💪
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int totalCost = 0;
for(int i=0; i
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.
Excellent, thank you !
The diff array works like a conservative field.
The partial sums work like a potential.
We start at the minimum of the potential.
en.wikipedia.org/wiki/Conservative_vector_field
n = len(gas)
s = 0
min_val = 1000000
min_ind = None
for i in range(n):
s += gas[i] - cost[i]
if s = 0 else -1
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
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
Superb explanation, i was stuck with the brute force approach.
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.
This part can be best understood with an example for let us say
Gas -> 1 1 1 1000
Cost-> 999 1 1 1
Variation of Kadane's Algorithm
This makes complete sense, your way of explanation makes this intuitive now, THANK YOU!
This is a great solution and explanation thank you!
To be honest I don't think anybody here really understood 100% why this solution works.
Simplyyyyy superrrr......
Btw.. can it be done using sliding window also????
Thanks a lot for the explanation.
I figured it out (eventually), but F ME, this is unintuitive.
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.
"I know my explanation wasn't the best". Bro I got the full picture halfway through your explanation
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
Looks like kadanes algo we pick part with maximum sum
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 😂
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.
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;
};
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.
Could somebody help explaining this:
At 10:24, why does sum of gas >= sum of cost guarantee a solution?
Thanks!
it's useful to think in terms of the diff array. The condition that sum of gas >= sum of cost means that the sum of diff array >=0. This means that, there is at least one starting point from which you can iterate through the rest of the array (to be more precise, if starting point is i, you go over i, i+1, i+2 ,..., n , 0 , 1 , ... i-1, where n is the length of the array) while keeping the running sum >=0 (i.e. not running out of gas). In the example considered [-2, -2, -2, 3, 3], index 3 is the starting point, since you can go around it until index 2 and the sum of the array will always be >=0 (which means trip is complete). But of course, the condition alone does NOT tell you where the starting point is, that is done in a greedy fashion as described in the video
just brilliant explanation
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int gasSum = Arrays.stream(gas).sum();
int costSum = Arrays.stream(cost).sum();
if(gasSum < costSum){
return -1;
}
int total =0, start = 0;
for(int i=0;i
Just had an interview with this question. It took me more than 40 mins to come up with O(n^2) approach T__T
It's a tricky problem. I feel really surprised to find that there are quite a lot of companies using it to test job candidates. Did you get any comments or feedbacks from the interviewer on your answer to this question?
@@王梦如-f5f I got the feedback was positive because I could figure out and communicate well during the interview
@@nicolaurent5758 good to hear that!
Congrats! atleast you were able to solve it XD
no worries man. The brute force is actually a bit tricky as well since you have to figure out how to do a "cycle for loop". And it's almost impossible to think of this greedy method unless you already studied this kind of question before.
I find all the leetcode problems using greedy solution not related. Really hard to find a common way to solve them.
A correctness proof would probably make this explanation more intuitive
var canCompleteCircuit = function(gas, cost) {
let totalTank = 0; // Total balance of gas
let currTank = 0; // Current balance of gas
let startStation = 0; // Potential starting station
for (let i = 0; i < gas.length; i++) {
let diff = gas[i] - cost[i];
totalTank += diff; // Add to total gas balance
currTank += diff; // Add to current gas balance
// If current balance goes negative, reset the start station
if (currTank < 0) {
startStation = i + 1; // Try starting from the next station
currTank = 0; // Reset current gas balance
}
}
// If total gas is negative, it's impossible to complete the circuit
return totalTank >= 0 ? startStation : -1;
};
which topic isn't tricky anymore...
Thanks, great video
how do you prove that as long as you can start, then there must be successful to make a circle?
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..
Great video
I just want to suggest to use enumerate rather than range(len).
Agreed. But I would first zip together the gas and cost lists first
I still don't get why we don't need to go back when we reach the last index...
Nice explanation bruh
why did you set res to 0 if you dont use it in your code?
Thanks
How will this change if input didn’t say it is guranteed unique solution?
Is it Kadanes Algo?
Did i miss the explanation why you only iterate to the end of the array, and not to the same position? Except 100 times word “greedy”?
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.
Can you think of the gas and cost array as well? I feel there might not be a pair of gas and cost array where sum(gas) >= sum(cost) and also the condition of only one unique solution
it's a pity that slower solution couldn't be accepted
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
circuit_len = len(gas)
for start in range(circuit_len):
gas_lvl = 0
stations_completed = 0
while stations_completed < circuit_len:
station = (start + stations_completed) % circuit_len
gas_lvl += gas[station] - cost[station]
stations_completed += 1
if gas_lvl < 0:
break
if stations_completed == circuit_len:
return start
return -1
Thanks!
Thank you so much!
34/40 passed but time exceeded for large inputs :(
is this the most optimal solution?
There really must be a better way to approach Greedy problems in general :(
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
Interesting solution. One note though I don't think we actually need the for loop in canCompleteCircuit. If we dont return on the first if check we're guaranteed a solution