Shortest Subarray with Sum at Least K - Leetcode 862 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem shortest subur with some at least K before we get into the problem I wanted to quickly mention that unfortunately this might be one of my last elak code videos for a while it's not that I don't want to keep making them I genuinely enjoy making these videos I don't really do it for the views but I have a lot of other obligations currently it's gotten to the point where I just don't really have the time to continuously make these uh videos for the last several of them I've been kind of sleep deprived today I am too I feel like then the quality kind of goes down but uh let's see how good we can make today's video I'll do my best as always we will be doing two solutions in this uh video both of them will pass the problem quite frankly the second one for me was uh more easy to come up with this one is going to be more optimal I don't want to like spoil the time complexity for you I'll just say this one is more optimal um and this one is pretty good this one is very easy to understand so that's why I'm starting with this one just in case some people find this one too difficult to understand for me though this one is a bit more easy to come up with rather than this one so we're given an integer array of nums the single most important thing about this problem though is that those nums could contain negative values and that's actually the only difference between this problem and another problem that we've solved before if you just head over to n code iio I think going to the N code all list uh somewhere here minimum size subarray sum this is the problem it's very similar to today's problem the only difference is that this one can only contain positive values and that makes a problem very trivial to solve with a sliding window but if we try to solve today's problem with a sliding window we're going to run into some issues let me show them to you first of all the problem states that we're given some numbers suppose I gave you this array one 12 one and I gave you a k value of two what the problem says we want to find the minimum length of the subarray that has a sum greater than or equal to the K value so in this case it's pretty obvious this is the array and we would solve it pretty trivially with a sliding window approach because if we knew all the values were positive we could do something like this we could have two pointers left and right the right pointer will tell us the ending of the subay so I want to find the shortest subay ending here that has a sum greater than or equal to K right now my sum is one that's not good enough so we know that we should expand the window we move the right pointer over here and we know that by Shifting the right pointer we're only going to be increasing the sum of the subray now the sum is three okay that's good we're greater than K the length of the window is two now I want to try to minimize it CU I want to find the minimum size of the subray ending at this position rather than like brute forcing it with an n s solution I am optimally solving it with a sliding window and now I'm going to shift my left Pointer while the sum is greater greater than or equal to k i take the left pointer and shift it over here getting rid of that my sum is now two still and that's the smallest window we could like continue with this problem but we're going to get the right pointer over here and that's going to be a bigger window now if I change the problem very slightly just by making this guy a negative that solution won't work anymore let me show you why two pointers still sum is currently negative 1 that's not greater than K okay shift the right pointer sum is currently positive 1 that's still not greater than K so now now with that previous approach we're going to shift the right pointer over here and now we have a sum of two so this is the window this is the window that we found and now we're going to try to shrink the window given the solution I said earlier so shift the left pointer now here okay this window is good enough the size of that window is two shift the left pointer again over here and this window is not good so we say that this was the smallest window but we know that's not correct this is actually the smallest window what went wrong this is what went wrong when we had the right pointer over here our guarantee is we're going to find the smallest sub rate ending at this value but that's not what we did we saw that the current sum is already less than K so we said that okay there's no way that shifting the left pointer is ever going to increase the sum that's not true in this problem because we could have negative values we could have a negative prefix that we could remove from the array so let's see how we can try to address that consider this input array where K is equal to 3 we still want to try that same idea because we know that the best we can do with like a brute force is n squ let's at least try to do better than that let's see if we can find for any arbitrary position the smallest subarray ending here with a sum greater than or equal to K if it's possible how could we find that faster than in linear time without having to scan through all of these what are we even looking for what are we trying to do well we have this entire portion we're trying to find the furthest to the right we can put the left pointer for example like over here such that the sum of that subarray is greater than or equal to K and consider this as well the sum of like this entire thing right now here the sum is 4 - 2 which is 2 that is actually not greater than k but we know that there still might be a subay ending here because we could remove a negative prefix and even if the um subarray sum was positive like just imagine for a second that the sum of this was four just imagine I changed the numbers around so that that would be possible four is greater than three that's like this entire thing but still there might be a prefix that is positive or negative that we could remove that would still keep this greater than or equal to three maybe we remove a negative number then this guy is actually going to get bigger it'll be five that's good but maybe we remove a positive number maybe it was positive one that we removed and then okay our sum got smaller it was minus one and then it'll be three but still we are greater than or equal to K so it's pretty obvious in either case the prefix that we would want to remove is the minimal one or at the very least we favor minimum prefixes but at at the same time we favor the longest prefix cuz if I could find the minimal prefix that satisfies this condition that I was talking about and I could maximize the length of it that would be very good for me because then we will minimize the size of the subate ending at this position okay so now you probably believe me uh you get the idea and sorry I think my camera was covering over here I had the word longest uh sorry about that we want the longest prefix but I'm sure you guys heard me say that word so okay that makes sense so now how exactly do we do this well to find the minimum among all the prefixes only among the prefixes that we visited so far I guess we could use some kind of dynamic data structure to do that because we can't just do the Sorting up front like we can't continuously sort the prefix sums cuz when we're here we only want to consider these prefixes not any that go further than that so a dynamic data structure would be a heap that we can use for that okay so theoretically it sounds sounds like it could work what's that Heap going to store well in my case I'm going to store a pair of values I will store the prefix sum and that's really going to be the Sorting key the prefix sum because remember we favor smaller prefixes and I'm also going to store the ending index for each prefix sum because I want to know like the index that it ended at so then I can say okay well if I remove that prefix then this is the length of my window now but if I do it this way why does it work because think about this this is what I'm saying I'm going to do as I'm going I'm going to say okay this is my current sum now like a prefix sum I'm going to throw it into the Min Heap and I'm going to keep doing that as I go so this one and this one and eventually here and now uh let's consider this while there are prefix sums in the Heap let's say while the minimum prefix sum in the Heap right now the minimum would be so this is Nega 1 this is positive 1 and this is zero so the minimum would be this prefix if I remove that from my current window my current sum right now is equal to two and the prefix is ne1 If I subtract that I'm actually adding one so then I'll be equal to three that's greater than or equal to K so that would actually be good so what we're going to say is okay now this prefix is going to be removed from the Heap we're saying that at this position this is where my right pointer is if I remove this prefix this is a valid window there actually might be more prefix sums in the Heap that we could remove it's possible that there's another prefix sum like this one that maybe it doesn't have the minimum prefix sum but still it is sufficient where we uh subtract that prefix that the sum of the remaining portion is still greater than or equal to K that's not the case here because you can see that by doing that right now our current sum would be then positive 1 that's not greater than or equal to K so we're not going to pop any further from the Heap so I'm saying we're going to use a loop to pop from the Heap not just an if statement but after that Loop is complete among all of those prefix sums we will use the ending indexes to calculate the length of the window and we will guarantee to find the minimum window ending at this index R so just believe me that we'll be able to do that if I did that and let's say this was that array I have it that's great but I popped a prefix sum how do I know that maybe further down the line somewhere further into the array maybe I'll want to remove that same prefix sum but we already popped it so what should we do add that prefix sum back no think about what you just said well think about what I just said why would we do that because ultimately what we're trying to do is find the minimum subarray and if I removed this prefix and I'm here right now my R pointer is over here this was the subarray if I remove that same prefix for when my r pointer is like further to the right the resulting array is actually bigger than what we already found so yes we might actually miss some subarrays like this approach is not guaranteed to find all the subarrays but we guarantee that those won't be the minimum sub rays that end up being the result anyway so that's why this approach works I think that's probably the critical most point about this approach and honestly that's why it was a bit unintuitive for me so if you're not a fan of this solution you might actually prefer the next solution I'm going to show you after we get done coding this one up but I think you can tell that as we are iterating through this array that's going to be Big O of n but we're not going to have to do that second scan so it's not going to be n * n but we are going to be pushing and popping from a heap so it's going to be log n let's code it up now we are told that we actually want to return a negative one if we cannot find a subarray that has a sum greater than or equal to K so I'm actually going to initialize the result to a very large value so we can try to minimize it but if we can't if result still equals infinity um return ne1 otherwise return uh the actual value stored in result okay so now I'm going to have my current sum I was talking about really this is going to be storing the current prefix sum but I think current sum is a fine name and I'm going to have a minimum Heap initially it's going to be empty I'm going to have it store a pair of values which is uh the prefix sum as well as the end index then I'm going to have my R pointer going through every position so for this right value I want to try to find the shortest subay ending at this position well first I'm going to update current sum that's pretty easy to do we'll just take the current value and add it to that now it's possible that we actually don't even need to remove a prefix sum it's possible that the current sum is already valid in which case we are are going to at least consider it as a possible result candidate so I'm going to say if the current sum is greater than or equal to K let's potentially update the result the result would be this we're trying to minimize it the current window that we're considering since we didn't remove a prefix yet we're kind of considering the entire prefix so we will just say the size of that is going to be I believe r + one since uh indexes are zero based um but there's that but now is the part where we might want to consider some prefixes from the Heap and from the drawing explanation this might not have been clear but the prefix sums aren't going to necessarily be like in order like this is the minimum prefix sum this is the second minimum prefix sum this is the third minimum prefix sum in this example but that's not always going to be the case when you have negative values um if I change this to like a -2 for example now this is the minimum prefix sum this is the second minim minimum and this is the third minimum well I guess this and this one are actually tied so the prefixes are happening out of order that's what makes this a little bit tricky that's why we're using a heap so this is the part where we're trying to find the minimum window ending at R I think it's good to try to think of it conceptually in those terms so now I'm going to say while my Min Heap is non-empty I want to look for a prefix and let's see if the calculation works out the minimum value currently in the Min Heap at the root of the Heap and we're going to get the first value in that tupal which is the prefix sum so we'll say zero and then we'll say okay the current sum minus this prefix sum if I remove that prefix sum am I still greater than or equal to K if so let's pop from the heat pop that prefix sum do this pop it we'll get a pair of values one will be the prefix and second will be the end index and I'm going to use the end index to calculate the size of the window if we were to remove that prefix and the calculation can be done by taking the right pointer minus the end index and in this case we actually don't need to do the plus one because this end index is not inclusive if you don't understand what I just said this is what I'm saying if we had let's say an array like this I say this is where my right pointer is and I say this is where my end index is like at two I think it kind of makes it obvious why we're doing right minus end because we're not including the prefix we're only including the remaining stuff so we got that size of the window and we want to try to see if it's the potential result so try to minimize this and this after we are done with that don't forget to take the current sum which is the current like prefix sum and push it to the Heap after you're done with this Loop very important to do that after non empty subarrays can't have values and since K is always going to be positive a non-empty subarray wouldn't be valid anyway um so we'll say Heap Q Heap push to the Min Heap the pair of values which is the current sum and the ending index which is R there you go you can see that this is a relatively simple solution to understand but in my opinion not one that's easy to come up with you can see here uh on the left that it does work it's relatively efficient but there is actually a linear time solution for this problem remember what I said earlier that I ideally we are trying to remove the prefix sum that is the longest and that minimizes the sum cuz we're trying to make the sum of like the subay at least bigger than K so this is ideally what we would try to do and if you understand this you can realize that the only prefix sums that we want to consider are the ones that are in monotonic increasing order let me show you why this is the case because everything else that follows is going to be relatively simple once you can really understand this point and not only understand it but why the key word why for a second let me change this example and make this number negative think about this for a second I have a prefix over here the sum of it is1 I have a prefix over here the sum of it is 3 I have a prefix over here the sum of it is -4 now take another look at what I wrote down here and think about this very carefully and if you don't want to think about it let me tell you what the observation is if I'm over here we can see that these prefix sums are actually in monotonic decreasing order do we really need need these three prefix sums because remember why would I remove a -1 prefix sum that is smaller than the -4 prefix sum that is bigger this one gives us the best of both worlds why do I care about these two prefix sums I don't if I'm over here and I had the choice between removing any of these three there's no reason I would ever remove -1 rather than removing ne4 remember removing ne1 will increase the sum by + One removing -4 will increase the sum by plus4 and it'll make it smaller so there's no reason I would ever want to remove this and consider this array even if it was valid when I could remove this and this will also be valid because if this is valid it's guaranteed that this is also going to be valid if I added one to this and it made it valid adding four is definitely going to make it valid as well so okay now you believe me that that we only need to consider the prefix sums to be in monotonic increasing order and by the way this is kind of a very tricky concept to wrap your head around if this is the first time you're introduced to this concept I would highly recommend heading over to NE code. and heading over to the snack section and specifically solving this problem daily temperatures it'll be a nice introduction to this concept of monotonic Stack um if you kind of scroll down you can see we have Brute Force then we have the stack approach and I think probably the will uh be most helpful if you're a beginner and then this hard problem is also a good one for monotonic stack so knowing what we just talked about and assuming you already are familiar with the monotonic stack pattern cuz it's kind of necessary to be able to I think solve this problem if you've never heard of it it's going to be pretty damn hard to do this I'm not going to lie but now I'm going to try that I'm going to try the monotonic stack so this is what I'm going to do I'm here my sum is1 and I'm going to add that pair here this is the sum it's -1 the ending index is zero remember this is the ending index and currently this is A-1 not greater than or equal to K and now we're here at two the current sum is going to be positive 1 I'm going to add that to the stack as well I'm not going to like show every single step here like how we would find the smallest window here I'm only going to show that when we get to this point so right now the sum is one and we ended at index one so that's where I'm adding this pair now I'm going to be over here the sum is zero and the ending index is two and now I'm over here the sum is two and the ending index is three before I add this to the stack now now I'm going to show you the step how would we now with this stack find the smallest subarray well first of all this stack is not monotonically increasing so that was already one thing I guess that's kind of on me when we added this second one when we were here this third one actually we should have checked the top of the stack and compared the sum with the top of the stack and we see that since this one is smaller than the top of the stack we should pop the previous one because remember we want to minimize the sum like the prefix sum and maximize the ending index and as we go further and further the ending index is only going to increase so we already know that that's why we favor keeping this one on the stack and uh removing this one okay so now I'm back here again uh sorry about the detour but we're at this ending index we know that like this is the Tuple that we are considering like the sum of it currently is two and the ending index is three we're specifically concerned with the sum right now we're trying to now minimize this what is the minimal prefix that we could remove that would possibly make the sum valid the sum right now is two well we know that the stack is in monotonic increasing order so where is the minimum going to be it's going to be all the way at the left of the stack so we can go through the stack left to right now as we go through one like for example this one we see okay -1 minus from pos2 that's going to give us three and three is valid it's greater than equal to K so okay so we can actually remove this from the stack now because remember like we're not considering that prefix anymore you probably see the problem here we are adding to the stack from this side and we're potentially popping from the stack from this side as well and we are now trying to remove from this side of the stack as well so that's the issue and that's actually why we can make a small modification to this approach instead of using a stack we can actually use a deck because then rather than removing from the beginning an O of end time with a stack it's actually constant time with a double-ended Q so now you understand at least in my opinion why this one is at least kind of approachable like this is the one I was able to come up with by making the monotonic observation and then making the stack observation and then realizing okay well stack is not actually going to make it more efficient but maybe a deck will so that's all the intuition behind the problem I'll try to run through the rest of this example assume we have a deck here I'm going to pop this and I'm going to say okay well that was this window we got the ending index we have this index 3 minus Z the window was of size three so that's the smallest window we've found so far and now I'm going to try again reading from the leftmost value of the deck it's this one the sum of it is 0 2 minus 0 that's not greater than K unfortunately so we're actually going to leave this guy in the deck so that would refer to this prefix we'll leave it in the deck but we will take the current prefix now which the sum was two and uh yeah the sum was two and the ending index is three and we'll take that and uh we will append it to the Q here so three or sorry two and three now we will shift the right pointer here we're trying to look for the smallest window ending at this position the current sum is going to be uh it was two and now we added three so it's five okay so it's already greater than or equal to k um but can we try to minimize it well let's start from the left side of the deck let's see this guy can I remove this prefix well 5 - 0 is still greater than or equal to K so yes you can remove that prefix now we're not considering that one anymore and that's popped uh can we keep going can we remove this prefix as well that would refer to this thing and that has a sum of two uh my current sum right now is five 5 - 2 is still greater than or equal to K so this was the smallest possible window the length of it is one that's what we would return for this example and you can see that all the operations that we were doing appending and popping from the Q were constant time we just scanned through the input for the record this is not a magic solution and I just realized that my camera was probably covering this Tuple over here it was 2 three sorry I know I said it but I guess it's hard if you guys can't see it so I apologize for that but like I was saying the reason I was able to come up with this approach is because I've actually seen this problem before I've seen this pattern before and yep you guessed it it is in the ne code 150 list it's actually part of the sliding window section sliding window maximum it's definitely a difficult problem that's why it's the last problem in the section but if you go to it you can see it has several Solutions Brute Force segment tree that's a difficult solution Heap a dynamic programming and finally the deck solution which is the one that I pretty much did in today's problem pretty much what I explained so if you were looking for a similar problem as today this is the one uh let's cat it up now so I'm going to start with a bit of a boiler plate here as you can see but now we're going to change the Min Heap to actually be a double-ended Q I'll call it a Q and it'll be like this but the pair of values it's going to store is actually still going to be the same and the rest of the code is actually still going to be the same as well I probably could have left that first if statement in if the current sum is greater than or equal to k then we can potentially update the result minimize it set it to itself or r + 1 and then we want to find the minimum valid window ending at R and so this time we can do that with the Q so we'll say while the Q is non-empty and the top of the Q or rather sorry the left part of the Q we go left to right because it's in monotonically increasing we're trying to remove the minimum prefix so left side of the que and now we want specifically the prefix sum so we'll get the first in that Tuple and we'll then say Okay current sum if I were to subtract this prefix sum am I still greater than or equal to K or maybe I'm newly greater than or equal to k then well if that's the case we're going to pop from the que don't need to consider that prefix anymore um I'm going to have prefix and end index and going to minimize the result the same way as before just like this right minus left uh actually not minus left sorry not thinking minus end index now is the part where you would think okay well now to the Q I just want to append the new tupal the current tupal which is the current sorry I can't type current sum and the ending index R but remember we do want the deck to be in monotonic increasing order so we do have to add that validation step validate the monotonic deck so say while the Q and while the top of the Q or rather the right side of the Q and in Python you can actually get the rightmost index with negative-1 otherwise we could just take the length of the Q minus one but I'll use Nega 1 and we're going to specifically look at the prefix sum so zero and while that's actually greater than the current sum I'm going to pop from the Q pop not pop left pop to the right so just do q. pop like this you could also say greater than or equal because if there's like a prefix sum that came to the left that was equal we would favor the one that came after it but it doesn't matter it'll work both ways so you could remove this as well I'll just prove it to you um and then running this on the left you can see it works and this time it is pretty efficient I know I know someone's going to say it's only 40% who cares I promise you this stuff doesn't matter please believe me it doesn't matter this is the most optimal solution if this doesn't pass you in the interview I don't know what will