Find if Array Can Be Sorted - Leetcode 3011 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find if array can be sorted the idea is relatively simple we're given an array of positive integers and we want to sort them well I guess we want to determine if it can be sorted if it can will return true otherwise will return false but the criteria for sorting this is actually interesting first of all we need to know the number of set bits within each integer for example eight looks like this in binary representation and so like everything else is going to be zero so the number of set bits within eight is going to be one so let's just assume that we have the number of set bits for every integer in this problem because that's not really where the complexity is going to come from if we really wanted to we could just get the count of bits for each integer and we can do that in linear time and then we can just store them in a hashmap if that's all we care about just being able to map a number to the number of set bits that it has so I just uh quickly put the number of bits for each of these numbers now they mentioned that the main operation that we can do is the Swap and we can only do it with two adjacent elements so for example let's say these two they're adjacent we can swap them but there's one more condition they have to have the same number of set bits only then are we allowed to swap the numbers okay so we want to know if we can sort this or not just going by these rules let's try a simulation let's try to sort it and see if it works if we're only allowed to swap numbers we can try to implement a sorting algorithm like this let's start at the beginning we can compare 8 with the value to the right of it which is four now 8 is definitely greater than four which is not what's supposed to happen we want this to be sorted in ascending order the smaller element should be over there so clearly we perform a swap here but before you do that you have to make sure that the two numbers have the same number of bits that are set and this time they do so we can perform that Swap and we'll get four here and then eight over here and we'll do the same thing we'll continue scanning from left to right trying to put this guy in the right position well it's definitely greater than two let's swap these two and we'll get something uh like this eight will be over here and then once again we will compare it to the value to the right okay 30 is greater than 8 so there's no need to do a swap here but we can still continue iterating and then by the time we get here we get to the end we look at these two elements and we say that okay well 30 is definitely greater than 15 these should be swapped well do they have the exact same number of set bits yep so we uh swap these two 15 and 30 the the algorithm I'm implementing here if you've noticed well I guess that was one pass through this the second pass would be like this where we start at the beginning and then we continue going up until the end of the array except now we can actually skip the last element why is that because the algorithm I'm actually showing you right now this dry run where we can only like swap adjacent pairs is actually pretty much a sorting algorithm you might have heard of it's called bubble sort it's a pretty trivial sorting algorithm it runs generally in N squ time in the worst case but if the input array was already sorted we could have actually gotten it down to be a linear time algorithm but uh the reason it works like this is because if you notice the main thing that we did with the first pass like we started with eight and we ended up shifting eight all the way over here we didn't continue shifting eight because there was no need to the elements here were already greater than 8 but we still kept going then we eventually got over here we're at 30 and we swapped it with 15 so after we're done with all of that the main guarantee with bubble sort is that well now the last element at least this portion of the array is definitely sorted because if there was an element that was bigger than 30 it would have ended up in this spot we already went through all the elements none of them were greater than 30 and now we know that for sure and so the next thing the bubble Shar algorithm will do is it'll find the second largest element among all of these and that element will go over here and it happens to be 15 and and in this example we can actually sort the array I won't dry run through all of this but eventually you will realize that the array can be sorted if we ever got to a point where we wanted to perform a swap but the number of set bits did not allow it that would be a problem for example if 15 was instead a 14 I'm pretty sure that does not have four bits set I think it has like three bits then we cannot swap these two elements even though this one is bigger than this one in that case we would return false so I'm not going to code this approach up from scratch but I'll quickly walk you through the code of it so I actually just copy and pasted this from like the editorial but it's a pretty a standard algorithm so we have the length of the input we create a copy of it that's not actually required in this case and then we have the outer loop it always starts from the beginning of the array but the reason we have this N - I -1 well the minus one comes from from the fact that we don't want J to be at the last index because we're doing J + one and we don't want to be out of bounds the minus I comes from the fact that we're skipping an increasing number of elements from the end of the array and so we just do two things here we first check if the elements are already in order in which case we don't need to do anything so we can just uh continue and get rid of this else cuz I don't know why it's in an lse so I'll just get this out of there this here they're using a built-in function to count the number of of ones in the binary representation of this number and also the number at J + 1 and so if they both have the same number of ones we will just swap the elements otherwise we'll return false if we never return false then we can return true out here there's one small change you can make a small optimization I guess which is basically uh just to kind of get some space up here we can create like a temporary variable which I'll call my flag I'll initially set it to false and it'll basically tell us if a swap has occurred here so if we perform a swap let's set that flag to True like uh this and then if it's set to True after we're done with this entire Loop that means we performed a swap but if we did not perform a swap if flag is false if not flag well then we did not perform a swap what does that mean well the only reason we wouldn't perform one is if the array is already sorted so we can just return true from here or we can break out of the outer loop and then return true down here so I wonder if this code will actually work it looks like it does pass but there is a more optimal solution let's get into it when you come back to the problem and actually think about it for a second not just doing the Brute Force but actually thinking about the problem let's take a look at it I have this portion of my array forgetting everything else I know for sure just by looking at it that this itself self can be sorted why is that because I have a block of continuous elements and the fact that they're continuous is important because we're doing individual swaps on adjacent elements so these are all continuous and the fact that they have the same number of one bits set tells me that this forms a continuous block or a sequence or whatever you want to call it subarray it does not really matter what these numbers numbers are whether they're in order or they're not in order it does not matter as long as they have the same number of one bits set we are good this subarray is going to increase and increase and increase and if these have one bit set as well it's going to keep increasing but what happens when we get here if we're trying to create a sorted array what should we do now these do not have the same number of bits set so if we need needed to swap these we would not be able to swap them how do you know if you need to swap them well it's not just about the element over here actually because consider this like instead of this being a 16 I'd rather make it a 32 I'm pretty sure that also has a single bit set so this array can also be sorted into 2 4 32 but now when I get here to 30 well this is bigger then an element in my first block I already know this element cannot belong to this subarray so we have to kind of perform a split and by split I mean that none of the elements here will ever be able to cross this line and vice versa and the reason for that is the one bit count okay so now that I have to create this line I still want to know if I can sort the entire array so then how do we do that well consider this for a second we're going to have potentially a big array and let's say we already knew the split points like there's a split here and a split there whatever the order of elements like we know individually this can be sorted this can also be sorted this can also be sorted and this can also be sorted now we need to know can the entire thing be sorted well how would you know that I guess if I've sorted this and let's say I have like three elements in there and I sorted this and I have two elements what do I need to do to know that this entire thing can be sorted well if the maximum element in the previous subarray is less than the minimum element in the current subay well then these two can be combined and can also be sorted so this problem is just a matter of doing what I kind of just mentioned splitting up into like these sub arrays not literally splitting it but just kind of keeping track of the split points like we'll know we reach a split point when we have different accounts like this and so like suppose we're just going through this array we go through this we find the split point and there's no violation like this element is not bigger than this one or actually we won't even uh perform that comparison until we're done with the second group so just to be very very clear let me show you exactly what's going to happen we're going to go through let's say the first group and I know the size is technically different than what I have above but just bear with me we'll go through this okay this is sorted great and then we get to this split and that's when we will continue then we'll go through the second group and then by the time we're done with the second group now we actually have a real previous group to compare the current group with when we were here we actually didn't have a previous group so for that we'll have some default values but here what do we want to do we want to compare the values so for the previous group we will maintain whatever the previous Max was of that entire group of the current group we will maintain the current minimum but we'll also maintain the current Max because we're going to eventually assign the current Max to the previous Max once we move over to the next group that's the main idea behind this problem coding it up is actually easier than you would think so let's just jump into that this will actually be the linear time Solution by the way and we won't need any extra data structures I believe so it should be constant space before we get started the first thing I want to mention is just how we're going to count the bits in each number I'm just going to create a helper function for that let's call it count bits it takes a number n and if we want to do it like the oldfashioned way we could do something like this where we shift it to the right and we have like a result and we increment the result every time we see a one bit set like this and then return the result that will work and this is actually one of the leak code easy questions I think in the ne code 150 list but there's actually a built-in way to do this python has a function Bine bin whatever you want to call it takes n and then it'll return a string I believe which we can count the occurrences of one within that string which will tell us the number of bits set so very clean solution so now we have that out of the way we can get into the rest of the problem I mentioned we're going to have a few variables not too many current Min and current Max initially let's just set that to the first number in the array we'll also have a previous Max we can't really set that to any element in the array so we will set a really small value a negative Infinity because every value is going to be technically be greater than that so we will not have a violation at least for the first group and then we'll say for n in nums we want to count the number of bits for n so we can do something like this count Bits n and we want to know is this count the same as all the other elements in the current group not the values of the elements current Min and current Max are the elements themselves but the number of ones in those is all going to technically be the same so we can say something like this if this is equal to the count of bits of current Min or current Max it doesn't matter whether you do current Min or Max cuz the count of bits should be the same so if this is the same then the group will increase and we don't really have any pointers we're maintaining for the current group so all we really need to do is update the current Min and current Max those can be updated like this current men is going to be the minimum of itself as well as the current number same thing with current Max now if this is not the case then we'll do else that means these two numbers have a different number of bits that means we just reached a new subarray a new streak so what should we do well what's the current minimum of the current group that's this current minimum if the current minimum is less than the previous Max and the previous Max was in a different group and they have a different number of bits set well then we can't possibly swap these two elements and thus we can never sort the array so we should return false if that's not the case we can update the variables the previous Max will be set to the current Max and the current Min and current Max can also be updated what we're saying is n is not a part of the previous group N is a part of the new group so just like we did up here we can set current Min and current Max to the first number within this group which is just going to be n so this is pretty much the entire solution if we never return false we can return true out here but there's actually one Edge case that I'm missing what's going to happen with the last group the last group is always going to have this equality set as true whether we have a group of size one or more than one we will never execute the else so if I had a group that looked like this uh 222 and then 1 one one this part is never going to execute even though we know that this array can never be sorted we're going to end up returning true so the way to fix that is with the last group check manually out here if the current minimum of the last group is less than the previous then return false otherwise return true and if you really want to be fancy you can probably condense these but that'll make it less readable so if we're returning this uh we would want to return the knot of that which will make that this so not and then that and now we have a slightly less readable solution in my opinion but this one should also work and after running it on the left you can see that it does and this one is more efficient if you found this helpful check out n code. for a lot more thanks for watching and I'll see you soon