Subarrays with K Different Integers - Leetcode 992 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem subarrays with K different integers this is a fun one and at first it seems pretty simple we're given an integer array of nums and an integer K return the number of good subarrays and a good subarray in this case is defined as being an array where the number of distinct integers in the array is exactly K I don't know why they use the word different maybe it's to confuse you but really it means distinct as you can see from this array it has three distinct integers 1 2 3 so consider the first example here and let's say k is equal to two just like over here I won't go through the idea of you know there's n s different subarrays so at the very least that's like the root Force solution cuz I've kind of said that the last three videos but that line of thinking will actually be useful for this problem just like the previous ones let's think about it for a second so if this is the first subay this is the second subay now we do have two distinct integers before we did not now we do so this counts as a good subray we add one more element we still have two distinct sub Rays now we add another still two distinct subray so so far we've counted three we add this element here now we have three distinct elements so this is not a good subay so what do we do well based on the previous problems it kind of seems like a sliding window problem doesn't it keep track of two pointers right pointer left pointer and and at this point you can imagine we have too many distinct integers so let's start shrinking our window let's shift that left pointer pop one left pointer is over here we still have three distinct integers pop this left pointer is over here still three distinct integers pop this left is over here now we do not have three distinct integers so this is now another good subay with this method we counted four good subarrays now we undercounted we missed some subay so let's go back and Replay that portion figure out what we missed so in that regard this is pretty similar to yesterday's problem before we uh Replay that portion I want to quickly mention how are we going to keep track of the distinct integers how are we going to know that we have exactly K distinct integers or if we have too many how are we going to know how far to shift our left pointer how do we I know to stop at this point the easiest way the fact that it's distinct integers probably a hash map or a hash set is going to be useful the reason I'm using a hash map is because we are going to possibly have multiple copies of a given value so with a hash map we can say okay one we have two occurrences of one two maybe we just have a single occurrence of two like at this point that's why a hashmap is going to be useful and in terms of like shifting our left pointer when we have this entire window here we have two occurrences of one we have two occurrences of two we have a single occurrence of three now as I shift the left pointer I decrease the number of ones I decrease the number of twos I then decrease the number of ones again and now it's zero and once it reaches zero that's when we pop this and now we've gotten to the point where we only have two elements inserted into the hash map that's how we know this is exactly equal to K and that's how we know when we can stop so that portion is not super complicated that's the easy part but I want to quickly go back and Replay that portion and try to figure out how did we undercount the solution what can we do to correct that so this is the first valid subarray that we have so we count one we increase it to this point we count two we increase it to this point we count three as we're doing this we're only counting the subarrays that start at this element and so far we've counted three of them once we reach the three over here we realize there's no more subarrays starting at this element there just cannot be right it's impossible at this point as we add more elements there's only going to be more elements introduced into the hashmap so we have to stop we have to then shift our left pointer we shift it let's say over here now this is still not valid but if you think about it that doesn't necessarily mean there aren't any good subarrays starting at this element so that's what we're missing we missed this this subarray and this subarray as well not only that we missed this subarray as well so I just pointed out three sub rays that we missed our original count was four if we also counted these three subay that we just missed then our total would have been seven and that's what the result was so how can we devise a solution that will actually get us there well it's going to be kind of hard considering it from the perspective Ive of counting subarrays starting from each element Because by the time like we start here left pointer is here that's great right pointer got here here here and then finally here so we counted those three sub Rays that's great as I shift the left pointer here now it's going to be kind of hard to know how many good subarrays are starting from this left pointer even if we ignore the three for a second we don't necessarily know how many good sub rays are going to be starting at this pointer because even though in this example it's pretty simple it's 1 2 that's not always going to be the case consider a slightly different example consider if I change this to A2 one now in this case how many subarrays are starting from this element well this is not a good subray so actually we only have one good subarray by swapping the order of these two elements instead of of having two good subarrays starting from here which would be these two we only had one so the order of those elements matters it's getting kind of complicated now so let's think about it from the other perspective now instead of thinking about it starting from each element let's consider the opposite let's consider counting sub Rays ending at each element let's just see if maybe that makes it a bit more simple for us I want to know how many good sub Rays ending at this element well uh so far we just have one distinct integer one maps to one so it's not a good subrate yet next pointer our right pointer is going to be over here our left pointer stays here our right pointer is here now we have two distinct integers how many good subarrays are ending at this element well just a single one it's pretty simple by the way not going to update the hashmap just to keep things simple for us this is a hard problem so I assume you know how to keep track of like occurrences of each element so I will uh be ignoring this part for now I'm going to take the right pointer from here shift it over here how many good sub rays are ending at this element well I count one but I also count this one as well how do we know that how do we know that this is also a good subray because like I said if I swap this I make it a two then there's only one good subarray ending at this element what's the difference what's the difference between this example and this example well when you look at it closely it's kind of obvious we can shift our left pointer here and the window is still valid in this case right now if I shift the left pointer here well this was valid and this is also valid that would not have been the case if this was a two how do we know that we can shift the pointer because the count of this element is not equal to one it's greater than one that means we can afford to lose this and our window is still valid because we have two occurrences of one right now pop it it's okay we still are good Okay cool so continuing with this idea so far at this point I'm going to uh shift this poter here now we counted three sub Rays this one this one and then after Shifting the left pointer here we also count this one now let's continue with this idea we're getting close but I'll tell you we're still not quite there yet there still is an issue and let me show you what that is so now from here shift the right pointer here now this once again is a valid window so far we counted four valid windows and again we can afford to lose this too I'm going to shift the left pointer over here now this window is still valid so far we counted five valid Windows unfortunately even with this approach we missed one we missed counting a subay we're trying to count all the good Subs ending at this element remember that's what we're trying to do for for every element count the number of good elements ending at that subay we counted this one successfully we counted this one successfully but the fact that we shifted our left pointer made us miss this one so what can we do well this is something you probably wouldn't be able to figure out unless you had seen this pattern before this is called the sliding window with three pointers if you're new to this just kind of watch me go through it just absorb what I'm about to show you and then try to go back and understand it and implement it yourself I'm going to keep track of three pointers the right pointer the left far pointer and the left near pointer so initially the left far and left near are both going to be set here and same thing with the right the right pointer is also going to be set here now the right pointer is going to be over here this window is valid so of course we increment our result but we do not exceed K therefore we don't shift either of these pointers and we also don't have like an extra element so we don't shift either of these pointers again so these will both stay here for now now once again right pointer is going to be here now this is a valid window this is where things get interesting by the way now we have an abundance of ones we have an extra one so what do we do we leave the left far pointer over here and we take the near left pointer and then shift it to the right now now you can see why I'm calling it The far and the near pointer this is important because we're trying to count the number of good Subs ending at this element that's what it's all about and these two pointers are going to tell us how many subarrays there are because the whole purpose of the near pointer is going to be find the minimum window with at least K distinct elements so if we have an extra element over here well we're trying to shrink the window so move the near pointer up until this point now the far pointer will tell us the max window where we have exactly K distinct elements both of these pointers will give us a window where we have exactly K distinct elements but this one will give us the smallest window this one will give us the largest window now with these two pointers every time we update our result we're going to add to the result the difference between these so add to it a near minus far plus one the plus one comes from the fact that like suppose in this original case where both of these pointers were at this element of course the difference between them is zero but we still want to add a subarray so we add the plus one now in this case the difference between them is one and that would mean we have a subarray here and a subarray here so far our result is three now now once again I'm going to take the right pointer shift it over here does it look like we exceeded the number of distinct elements no so we leave our far pointer over here does it look like we have an extra occurrence of this element yep we have two of them so we take the near pointer shift it over here we are trying to minimize that window and now what do we add to the result the difference between near minus far plus one so we add three to the result now our result so far is equal to six once again we take our right pointer shift it over here and this is where things get a little bit interesting because now we've gotten to the point where we have two many distinct elements we have three distinct elements we are forced now to shrink the window and by shrink the window I mean shrink both of the windows and so instead of us we kind of have a choice we could shift the far pointer if we really wanted to but that would be a much more complicated solution I won't get into it we can be smart and shift the near pointer and watch what I do I say okay let's pop this element let's shift the near pointer over here now and now this window is valid also what we're going to do is just take the far pointer and move it all the way over here to match where the near pointer is because this is not only the smallest window ending at this element the smallest valid window it's also the small uh the largest valid window ending at this element so now these are equal this is a valid subrate so once again we add one to the result result is now equal to seven and that's of course the result that we're looking for this is again a difficult algorithm I wouldn't expect you to be able to come up with it by yourself and you might have to replay portions of this video but that's okay just kind of let the ideas here sync in try to apply them try to run it on a few examples of your own maybe on pen and paper or maybe if this makes sense to you try to code it up yourself this is a sliding window with three pointers the time complexity is Big O of n we do have a hashmap though so let's not forget to consider that space complexity as well let's code this up by the way you can see my notes here you can pause the video if you were curious how I was able to come up with the solution but I will say that part of the reason I was able to come up with it on my own is you can see here I solved it about 5 years ago myself so that definitely helped I think let's start with the easy stuff just kind of the initialization so we know we're going to have a hashmap I'm going to call it count I'm going to initialize it to a default dict in Python that just kind of makes it a little bit easier for us to code up I'm going to have the result which of course is going to count the sub Rays that's what we're going to return as well and we're going to have three pointers left far which is going to be set to zero initially left near which is going to be set to zero and we're going to have the right pointer but I'm going to use that within the for Loop like this because every time we see an element we of course want to increment the count of that element so the number at the right pointer is going to increase the count by 1 and of course if the number of distinct elements therefore the length of the count is exactly equal to K we did determine we can increment the result by taking the left near pointer subtracting the left far pointer and adding one this much we do know for sure now the other thing is how do we know when to shift the pointers well there's two cases where we would shift our pointers right while the number of distinct elements exceeds K that's one k where we're going to have to do some shifting there's another case though where we can try to minimize the window and the only case we can do that is if the count of the element at the left near pointer is greater than one we have extra copies of that element therefore we can shrink the window we can shrink the left near pointer let's start with this one I think it's kind of easier this would be pretty straightforward we would of course increment the left near pointer but not before we update the count of the element at that pointer so just like this decrement the count by one since we're only going to decrement the count if we have an extra occurrence of that element we don't have to worry about popping it from our hash map so that's why I said this is the easy part I started with it now this is the more confusing part but we know we chose to shift the near pointer so that's what we're going to do we're going to decrement the count of that element so the number at the left near pointer decrement the count and if it reaches zero if the count of that element reaches zero let's pop that element in Python it's pretty easy count. pop of this element at that left near pointer and of course we're going to take that left near pointer and increment it by one when this Loop is done executing we want to update our left far pointer but if we do it out here if we take the left far pointer and set it to left near out here well that's a problem because we only want to do this update if this Loop executed so the easiest thing to do is just move this line within the loop whoops Just Tab it into the loop it might execute more times than we need it to but this is just the easier way to code it up in my opinion so this is the entire code but don't let it fool you it's definitely not easy to come up with I'm going to run it to make sure that it works as you can see on the left yes it does it's efficient if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon