Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem number of subarrays of size K and average greater than or equal to threshold now I don't know about you but as soon as I read the name of the problem sub arrays of size K that immediately tells me that this might be a sliding window problem because that is an efficient way to get subarrays for larger arrays and in this case another hint is that we want the average of those sub arrays and a sliding window is a good way to not recalculate the entire sub array but we're given an array of integers and two integers K and threshold now K is going to be the size of our sub array so that's going to be the size of our window and the threshold is going to be the threshold value that our sub array needs to meet more specifically the average value of our subarray needs to be be greater than or equal to the threshold if it is we can increment our result we can count that towards our result because what we're trying to return is the number of these sub arrays that meet this condition so I think I pretty much dissected the problem already but let's go through an example quickly so given this sub array and given a window size of 3 and a threshold which I'm just going to call T four we want our average to be greater than or equal to 4 but our sub array has to be exactly of size three it can't be smaller because think about it one value like this five alone does meet the threshold but that's not what we're looking for we want the sub Rays exactly of size three not smaller than three so starting at the beginning we could do it like this where we just have one value so far but we want to keep growing this window until it's of size K we have two values and while we do this we're going to keep track of the average how do you calculate an average well remember two plus two divided by the length of the sub array which is 4 divided by 2 the average is two that's kind of obvious from just looking at this and when you add a third value well all of these are twos so the average is still going to be two but now our window is a valid length so an average of two does not meet the threshold okay now we want to check the next window we're going to increase it by one just like we've been doing but now our window is too large so before we even compare the average of this window to our threshold we have to remove a value over here and then we're looking at this window well the average is still two that's too small and once again remove this value and add this value so now we're getting more interesting our sum our total sum so far is nine this is kind of another hint that we should be keeping track of the current sum of our window because then we can easily calculate the average just by dividing by K every single time so the average right now is three that's still too small remove this guy now we have three values here a total of 12 divided by three is yes greater than or equal to the threshold four so we increment our result by one our result now is going to be equal to one remove this guy check this window our sum now is 15. by the way previously our sum was 12. so how would I update it I wouldn't just go through the entire sub array and sum every single value together what we would do is since we removed a 2 over here we're going to subtract 2 from this which is going to give us 10 and then we're going to add the next value which is a 5 which is going to give us the 15. so we can update the current sum in constant time that's just another supporting fact that the overall time complexity of this sliding window is going to be Big O of n now our total count of Windows that meet the threshold is 2 now and I'm just going to do this quickly we're going to get rid of this guy add this 8 so now our sum is going to be 18 divided by 3 our average is definitely going to be greater than 4 so now finally our total is going to be 3 that's what we would return you can see that's what they had over here as well so the problem is a pretty cookie cutter this is a pretty good example of the sliding window Technique we don't have any data structures we don't have any hash sets so in this case the memory complexity is constant so now let's code it up I'm going to start just by initializing the result I'm going to set it to zero now there are many many ways that we could code up this sliding window we could have two pointers left and right but I'm going to code this up like the cleanest way that I know how to do it which is just by using one pointer because if we have our left pointer and we go through the positions we can get the right pointer pretty easily just by adding K and subtracting 1 to it that will give us a window of size K every single time and we're gonna start at the big beginning and we don't need to go all the way up until the end because we only want Windows of exactly size K if we go all the way to the end we might get windows that are too small so we're gonna have our left corner go through every position in the array minus K plus one this makes sure that we go through every single valid position the reason I'm plusing one here is because in Python this value is non-inclusive so we need the plus one to make sure that we actually get to this length minus K index remember though we also need to keep track of our current sum now a shortcut I'm going to do is just sum the first K minus 1 values so that we don't have to do that here and because we're not even iterating through every position anyway here I'm gonna say the array up until K minus 1 I'm going to sum the array remember this is non-inclusive so we won't include the K minus 1 value here now when we have our left pointer going through the array we're going to add to the current sum the value at the array but we're not going to add the value at the left pointer because we've already added those values up here we want to add the value at the right pointer how do we get the right pointer how do we calculate it well we take left plus K minus 1. and then we want to check is our average how do we calculate that take the current sum divide by K is the average greater than or equal to the threshold it's important that we have that greater than or equal if it is then we increment our result and then remember as we pop the leftmost value we don't really have to update our left pointer because we're already doing that up above in the for Loop but what we do have to do is take our current sum and subtract from it the value at the leftmost index if this is confusing to you I definitely recommend trying to code it up in a simpler way like you don't get any brownie points for making your code AS short as possible usually in interviews I just wanted to show you this way the main shortcut I'm taking is just by initializing our window immediately and not having to iterate through every position in the array sometimes this technique can be helpful for more difficult problems but once we're done with that we go ahead and return the result now let's run this to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatco.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon