Longest Nice Subarray - Leetcode 2401 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem longest nice subarray and I would say this is a pretty nice problem we get a chance to go back to some of the basics um but probably the most important thing with problems like these is making the most correct observations in order to figure out what those Basics actually are when I say Basics I mostly just mean like which pattern does this problem fall into once you know the pattern then it's kind of just about filling in the little holes of how this problem or rather how this pattern can be used to solve the problem and to fill in those like little holes you kind of have to make those observations and really focus on the problem so with that out of the way imagine we're given an array of integers like this and we care about the binary representation of each of these numbers so just to make that easy for us so we don't make mistakes I've kind of made a table for each number down here and I think this really makes it easy if you were given a problem like this one and you had had no idea how to solve it you have no idea what observations to make at the very least you could make it a little bit easier on yourself and just draw out the binary representations of a few integers and then use that to see if there's anything we can notice about the problem but anyways let's first read the problem which is we're given these integers we want to find the longest nice subarray that we can and that's going to be a contiguous subay we want to return the length of it once we have determined what that that nice subarray is the longest one and we're going to do this by being given some positive integers a nice subarray is going to be defined as one uh this is an example of a nice subay three and 8 because when you take three and you bitwise and it with the number eight take a look at the binary representation of those numbers over here we see we have a couple ones with three and we have a single one over here with eight when we bitwise and these that's one of the major operations about this problem but there's a couple other bit manipulation operations we're going to need as well and I'll show you those in just a sec but for three and 8 when you bitwise and you check if both of the bits are set in that position and clearly we see that both of the uh bits for any of these integers are not going to be set meaning in this case I guess the word that I'm going to use for these two numbers is to say that they are non overlapping they do not overlap the binary representation of these numbers does not overlap and that gets to what this problem is really asking for it's saying that a nice subay is one that's defined just like this one where when you and every element together the result should be a big fat zero and now that you know what a nonoverlapping or a nice subarray is in this case let's look at the opposite one that is not very nice and that would be this one where we have one and three this is definitely not a nice subay because when you bitwise and these two together you see that these two bits are different but these two bits are the same if you take one and end it with three the result you're going to get is actually one in binary it would look like this 0 01 because that was a spot where both bits were set thus the bit is going to be set in the output because of that so again in a more simple way we could really just say we're looking for numbers that are nonoverlapping in a sense that's how I think of it to simplify this problem because that long description of making sure the bitwise ands result in a subarray of zero is a bit less straightforward and a bit less like human understandable so I'm just trying to make it easy for myself now that we have that now that we kind of know the trick behind this like that was the key observation in this case how do we go about solving a problem like this one well the brute force would be a roughly n squ solution where we look at every single subay and just check if the bitwise and of that subay is equal to zero and as long as it's true we are good but if it's not then uh it's not going to work anymore like if we got to this point for example we realize that this is not a good subay well we can't really continue any further I guess we could if we wanted to but if this is not a good subay like if these two overlap while adding more elements isn't going to change that these two guys still overlap so what we would do in that case is well just start at the next element over here let me find the longest subay I can from here and then I would go to this element okay I I get that and so far so good I look at the next element I get that and I think so far so good and then we keep going and I think the next element will not allow us to maintain the non-overlapping property it looks like this one does overlap over here so then we would stop and once again we would start over we would start at the next element and from here what's the longest subarray I can get okay here I got this and now I got 48 these are not overlapping and then I get the 10 it looks like the 10 is overlapping with the eight so again I would stop now that's the Brute Force I went through it a little bit longer than I do most times because I want the observation to at least make sense to you like I'm not just pulling this out of nowhere I think this problem makes it pretty obvious what the pattern is the pattern is clearly a sliding window why should we have to start all over again why should I have to if I started from three and I went all the way here and I say okay this is no good and then I want to start at 8 why should I have to recreate this subay over here when instead when I'm over here I can instead remove this guy AKA just slide my window so that's the idea I'll do a brief dry run right now but I also want to mention that if you're new to this pattern it's not trivial you can't expect to watch like a 5-minute video and then just completely understand this pattern and understand how to solve difficult problems using this pattern it's not that easy I highly highly recommend if you're a beginner to consider at least checking out n cod. it's intentionally designed just for people like you so that once you kind of learn the patterns once you I think the sliding window pattern is in this course but once you learn the patterns it gets a lot easier and there's plenty of resources you can use to do that if you want to use NE Cod iio that's great you could also use other resources as well so now I'm going to go ahead and do a pretty basic dry run what I usually do is initialize my two pointers at the first element the main thing we're going to track here is the current bits that are set so this Cur is going to be a number and it's going to be the binary representation of the bits that are currently set so so initially we can just say zero because none of the bits are set then as the algorithm goes the right pointer is going to be the one that iterates at each step at each step we're going to take this and increment it by one and move it to the next element we're going to increase our window so we look at the first element we want to know does this overlap with any other element in the current window to figure that out all we have to do is take our current window like this should be the current window and and it with this which is one and if this is non zero if this does not equal zero that means that the window is invalid but right now it equals zero because we have zero anded with one and the result of that is going to be zero they're not both one so so far so good I mean if you and anything with zero you wouldn't expect to get a a nonzero result so current ended with one is zero so we are good so what we do is say okay this window is valid it's a window of length one and thus we can go ahead and just keep the left pointer here and increment our right pointer I'll just scribble that out and move it over here now notice that our current is still zero but we don't want it to be zero at this point so this is where it gets a little bit tricky this is where we actually don't use the bitwise and operator to update our current window because as you can see if we start with zero then we can't ever set any of the bits in here I mean we can't do that with an and operation but there's another operation that we can do a bitwise uh it's not exclusive or it's actually just bitwise or to set a bit so it's pretty much that simple if you don't know what or is it's kind of the opposite so if we had like 0 0 and 01 something like that we only need a single bit to be set in a column to get a one in the output and if nothing is set then we still get a zero so basically like any bits that are set in this number will be moved here and they definitely shouldn't be overlapping so that doesn't really matter so we can assume that we'll have a way to update cerr so now CER will be one and next our right pointer is clearly at three so once again we will take cerr which is one right now and do one anded with three and we definitely will see some overlap it is not going to be zero that's bad so what do we do things get interesting here now is the part where it's invalid so we will shrink our window we're going to make it smaller by Shifting the left element so what we're going to do is while this is the case while take three and end it with cerr not just one but C we are going to shift the left pointer so we can easily shift the left pointer that's the easy part just move it over here but there's something you want to do before you shift the left pointer because now our window is just three before we shift the left pointer we want to unset this element so now the question is how do you unset a bit well let's think about this for a second I'll try to briefly explain it so imagine over here you have a number let's say our Cur looks something like this I have C and I'm just going to draw some random digits here this is my Cur I have a new element the current number that I'm looking at at index I maybe it looks like this it's 0 0 0 and then it ends with a 1 Z or something like this where this is is clearly overlapping so this is the new number and this was our previous Cur so we can see there is some overlap and we want to now take the leftmost element that was in our window and remove it so essentially what we're saying here is we want to make room for this bit which is overlapping with this one so what our algorithm is going to do is just keep Shifting the left pointer until this bit is available now if I had a number let's say my leftmost number at my left pointer looked like this it was the exact one that we want to remove it's just a one so it removes this bit so how do we do that removal well it's actually just the xor operator exclusive or we used or to actually set the bits but exclusive or is useful for unsetting Bits And the reason for that is this right now we have this number down here that I drew in red we only want to unset this bit over here we don't want to affect any of these so you might say that well we just use an and operator and between these two or do some kind of inverse and maybe there is like a way that you could make that work but xor is just a lot better because exclusive or means that if I do an exclusive or with this and this element then I'm just going to look at every number and if they're different I'm going to put a one in the output if they're the same then I get a zero in the output so you can see how like everything here that's a zero means that we're just going to copy all of the bits that are over here zeros will not change anything basically the property is this if you take X some number let's call it N I guess n and exor it with zero the result is always going to be zero that's an exor property so that's the reason why we do exor and also I want to make it clear from this picture why we are going to shift the left pointer before we take the rightmost element that we just saw and add it here because you can see what I had initially this this is my Cur this is the new element I'm trying to add but it overlaps with our current window so what I want to do before I and this here before I set the bits here rather I want to make sure I unset the bits first if I set the bits and I put a one here and a one here then I'm going to do the unsetting here and I'm going to end up with a zero over here that's not what I want so that's another uh key thing about this problem and I think that's pretty much it once you know that you can pretty efficiently solve this problem so right now our window is here haven't yet added the three to C but we recognize that c and the current element three let's use a different color C and three is not equal to zero so we will take the left element this one and exor it with cerr which will uh bring us back down to zero I think and then we will see that okay now we can take this element and add it to the window because now they are non-overlapping and our window will become this then we will start expanding the window we'll get eight we'll get 48 and so far we'll be good we'll try to add 10 it won't work then we'll start shrinking the window so we'll get rid of three and then this is what our window will be you can see that there is still some overlapping here so we will have to get rid of the eight then we will have these two elements remaining they do not overlap so this is our final window and then we would be done this is a linear time solution constant space let's code it up okay so let's just initialize the variables first I'm going to have my result which is going to track the length of the longest nice subarray we'll return that and then I'm going to have my left pointer which I will set to zero and then I'll have my right pointer going through the loop going through every position in the array and of course we will have our current window I guess you could call it but probably the more appropriate and common name for this is the bit mask basically like an integer where each bit is going to represent something you might be Ed to do something like this Cur ended with the current number but remember before you do this we have to check if the window is valid we have to do the other thing before we do that and actually we're never going to be doing current and that that's not going to update C the way we want to we're going to be doing or instead but anyways we're going to check while this number is non zero while this is non zero what we want to do is of course update the left pointer increment that but before you do that very important update your current number unset the bits that are set by the number at the left pointer by doing this after you're done with that we can pretty much safely assume that our window is zero and at that point we can potentially update our result like this result is equal to the max of the current length and the length of the current window which is right minus left + 1 and after don't forget to actually set the bits with the current number now because now we know for sure that Cur ended with this number is in fact Zero by executing this Loop we did that so to set the bits it's pretty easy you could do this Cur or with the number at index R so or is used to set bits generally and just to quickly run this now you can see here it works it's very efficient but there's one thing I wanted to briefly mention remember how this Loop was used to determine that current and this number are not overlapping so if that's the case the reason we used or was because we just wanted to make sure every bit in here is going to be set here whether the bits are set here or not but this Loop basically guaranteed to us that these two are not going to be overlapping anyway like the first number could look something like this the next number is going to look uh like this it has to it has to be nonoverlapping with the other one so it's actually fine here to use exclusive or as well because you can see then we're basically setting the bits all of them are going to be one in this example so I mean that doesn't really matter but in case you were wondering like why can't we use exor here I think that's a very fair observation to make and if you made that observation that kind of proves that you were really really paying attention to the things that I was talking about here anyways thanks for watching check out n code iio for a lot more and I'll see you soon