Longest Subarray With Maximum Bitwise AND - Leetcode 2419 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem longest subarray with maximum bitwise and so immediately from just looking at the problem we're finding the longest subarray so how many subarrays are in an array generally N squared so at the very least just from looking at the problem The Brute Force is going to be n s so automatically before I even know exactly what the question is asking for I'm thinking in my head how can we improve this how can we get it down to possibly and log in time perhaps we can get it down to linear time there are several algorithms I know that run in linear time on an array algorithms such as the prefix sums thing that we were actually covering yesterday sliding window algorithm TW pointers algorithm and in my head there's actually another algorithm that's heavily related to these two kadan's algorithm it also has to deal with sub Rays the same way that two-pointers and sliding window do and quite frankly this is PR ically kadane's problem the only difference is that instead of finding the longest subay sum the maximum subay sum the longest subay with the maximum sum we are looking for the longest subay with the maximum bitwise and actually I guess technically kadan's algorithm the maximum subarray problem it doesn't look for the longest subarray but in any case let me read the problem so this makes more sense anyway the idea is that we're given a array and in that array we want to find the the maximum possible bitwise and that we can create not the maximum sum that we do in the traditional kadan's algorithm but the maximum bitwise and so in kadan's algorithm we find the pattern of finding sums we find that if there's a negative sum we can remove it we cannot consider it so perhaps there's also a pattern when it comes to bitwise and so now let's get into the problem and quickly before I do I just want to mention that all of these like patterns and these kinds of things if you're new to them if you don't know what these words mean I covered them in my Advanced algorithms course I'm not saying like you have to buy it or whatever but thought it was worth mentioning so we're given this input array there's several sub rays that we could look at we only care about the sub rays that have the maximum possible and bit wise and that is so in this example the maximum possible bit wise and is actually three so this would be one example of a subray this would be a second example and this would be the third example among all of those sub Rays with a bitwise and of three which is the maximum bitwise and that we can achieve we want the length of the longest subray I just showed you there's only three of them this is the longest one the length of it is two therefore the return value is two okay now how do we figure it out algorithmically there is the n squ solution but is there an optimization that we can make it's actually simpler than you think so instead of giving you a really long explanation I'll give you a short one consider this we start with one this is what it looks like in binary representation take the the second number it's two this is what it looks like in binary representation bitwise anding them is taking the bits and if they're both one the output is one if they're not both one the output is zero they're not both one here as well so the output is zero here so now we just realized this we were here this was our subray this was the maximum bitwise and we could achieve one so far and then we got to two so now we're trying to find the longest subray so ideally bitwise anding these together with will give us the maximum bitwise and that we've seen so far but it gives us zero instead so what do we do well we kind of have to start over I mean this guy we want a continuous subray so we can't really extend this anymore so we should then just stop that so kind of like kadan's algorithm just kind of ignored the stuff that came before and now restart from here and by the way what is the bitwise end of a single number well it's two so now actually this was greater than our original maximum so so far the maximum wisan we can achieve is two I could continue this sort of simulation but this problem is actually simpler than that when you break it down let's now deeply consider what's going on with bitwise and consider an arbitrary binary number something that looks like this and suppose that this is our current bitwise and we are trying to maximize the bitwise and there are three scenarios one is that we come across a number that is less than our current number in that case it could be anything like it could be like this it's only one smaller like you took the one bit and turned it into a zero it could be smaller in any sort of way but the point is that if you take a smaller number and bitwise and it with a number the result is always going to be smaller than what we originally had so in this case we'd only get a one set here and a one set here it could have also been possible that this number had some one set in positions where this one didn't and in that case we'd actually just end up with a big fat zero well I guess they're the same here but you get the point if you take a bigger number bitwise and it with a smaller number the result will always be smaller than the bigger number what that means is whatever our current bitwise and is so far if we come across a number that is smaller than our current bitwise and at that point we cannot further extend our window we wanted to extend it we wanted to add this guy but no we can't it's just going to make our result smaller we only care about the maximum bit wise and so therefore now the size of our subarray is back to zero not even back to one it's back to zero because this is not a valid subarray so that's case one the new number is smaller case two and three are going to be where the number is equal and where the number is greater let's start where the number is equal so when you have two equal numbers the bitwise and of both of them is always going to be the same so if you take X bitwise and it with x X the result is always going to be X so okay so if we had a subarray with the maximum bitwise and so far that we've seen and now we come across a number that is the same as our current bitwise and well now we can extend it so now to our window we'd say size + one that's great the third case is a bit more interesting you come across a number that is actually greater than the current bitwise and it could look something like this where you know some of the bits are different some of the bits are the same but the most significant bit here the most significant different bit is a one in the second number or you might even have something that looks like this it doesn't really matter the whole point is that this number is bigger than this one and therefore the bitwise and of these two is always going to be smaller than this second number why is that for the exact same reason I told you remember this is the exact same as case one the only difference is that in case one we have had the bigger number on top and the smaller number on the bottom remember when you take a big number bitwise and it with a smaller one it's always going to be smaller than the bigger number so once again the result will be a smaller number but the thing is what do we do in this case this was our current sub suppose with a certain bitwise and well I guess to put it in more concrete terms this was our current subray with a two now we came across a three three is bigger than than two if we bitwise and these it's going to be smaller than three I think specifically the bitwise and of both of those would actually end up being two not that that matters we already know it's smaller than three so far the maximum bit wise end that we can see is actually three so what we want to do is now we were trying to extend our subro we can't do it we reset it not to zero this time we actually set it to one because this is bigger than the max that we've seen so far so now that we realize all of this we realize these patterns it has to do with the bigger numbers now take a look at this example one more time closely the only time if you were to go back and Rewind those three cases the only time we actually extend our subarray is when two adjacent values are equal and since we're trying to maximize the bit wise and we found that we're only looking for the maximum values so therefore this problem is just a more complicated way of wording the problem find the longest consecutive subarray with the maximum element within the array so all of a sudden this problem is actually very easy and very approachable for us so how would I solve it there's actually two approaches so I'll show you two different ways to code this up one is actually really easy you first just take the maximum of this array just find the maximum you can do that with a built-in function or however you want to do it the max is three in this case so we would look for the longest subarray with all threes so we'd look at the first element it's not a three we we don't care about it it's a two we don't care about it it's a three okay size of our window right now is one second value three add one to the size of our window so far the max window we have is two now it's two over here that's not three reset the size of our window back to zero but the current maximum that we computed our result is still two we want to maintain that so now we see a two skip it don't really care about the size this example is pretty simple but imagine that after that I'm going to kind of continue this array down here suppose after all those values we actually saw a few more threes and then another three and then another three so how would you code it well now that I've seen a three my current size is zero I'm going to increment my size now my size is going to be equal to one now I see a second three I'm going to set it to+ one now I see a third three I'm going to add plus one again and now it's finally bigger than the result the result will now be set to three now if I saw another three I would do the same thing if I saw a number that's not three for example two then size would be reset back to zero so let's code up this approach first technically it's a two- pass approach because we are pre-computing the maximum there's another way to code it up I'll show you after that so I'm going to get what I call the target this is just the maximum I'm going to take Max of nums the reason I'm not calling it Max is because that is a built-in function in Python I'm going to maintain two variables the size and the result as I just kind of showed and I'm going to go through every number in the input array nums and if n is equal to the Target just increment the size by one otherwise reset the size back to zero after each of those we want to potentially maximize the result so do it just like that and then at the end down here we're going to return the result um let me make sure I type it correctly this is the entire code a bit easier than you were expecting isn't it but don't forget that we kind of changed the problem the problem was asking for bitwise and but we're not looking for that anymore so let me run it as you can see it's efficient in terms of Big O time complexity this is linear we don't have any data structure so it's constant space but technically this is a two pass solution we did pre-compute the maximum there is another way to code it up I'll actually do that now it doesn't really require anything special just remember the three cases I'll summarize them for you here so I'm actually going to write out the variables first so we are still going to have the size and the result initially they're both going to be set to zero we're going to have an extra variable this time called the current Max going to set it to zero and we're going to iterate over the nums like this for n in nums at the end we're going to go ahead and return the result so what's going to go in between here is going to be determined by these three comments that I have up above remember that if the current number n is the current number is less than our current Max then the bit wise and of those together is guaranteed to be less than the current Max remember that if they're equal then the bitwise and of them is also going to be equal it's going to stay the same but if n is greater than the current Max it's the same as case one bitwise anding them together is only going to make the result smaller but we are going to handle these two cases slightly differently I think it'll just make more sense if I code it up I'm actually going to start with this one up here if n is greater than our current Max what should we do well our current Max is going to be n remember we're looking for the longest consecutive subarray with the maximum element n is our current maximum element so we're going to Set current Max equal to n we're going to reset the size down to one and we're going to actually reset the result as well it'll make more sense when I code up the rest of it but we might have been updating the result so right now I'm going to reset the result down to zero the other case is if they're equal well that's when we're actually increasing the size of our window so else if n is equal to current Max just increment the size by one lastly if n is smaller than our current Max then reset the size of the window down to zero and so the fact that we don't know what the actual Global Max of the array is means that we are going to have to update the max periodically like this so the result is going to be set to the max of what it currently is and the size at some point we might have saw a streak of twos like we might have had an array that looks like this four consecutive twos at that point our result result would have actually been set to four the longest subarray with the max value is four but eventually we'll see three three is bigger than two that's when this guy is going to evaluate and it's going to say reset the size back to one our current window is one not only that but reset the result so it's pretty rare that we write code like this so I did want to go through it reset the result down to zero and this would still execute so the result would be set to one in this case and then we'd um execute this one when we get to the second three cuz we see two consecutive threes in a row so then size would be two and then the result would end up being two and then that's what we would end up returning this is the entire code you can use like these as the intuition but these are mainly to prove to you that we're only looking for the max element and we want to know how many consecutive times it appears the maximum number of consecutive times it appears I'll run this now well whoops actually I shouldn't have done that this is not a comment let me get rid of that and then rerun it and as you can see on the left it works technically this one is the same in terms of Big O time and space complexity but it is a one pass solution so that's like the main benefit but I kind of prefer the first solution to be honest