Special Array with X Elements Greater than or Equal X - Leetcode 1608 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve this problem long name special array with X elements greater than or equal to X and even though it's easy it's a little misleading because this is quite an interesting problem we're actually going to go over two approaches for this problem one is going to be an N log n solution and the other one is going to be a linear time solution both of them are actually pretty interesting in my opinion so we're given an array of non- negative integers the idea is that for an array like this one 35 this is considered a special array because there exists some number that we call X such that there are exactly X elements that are greater than or equal to X in the input array is that number one no it's not because there are two elements greater than or equal to one in the array so there's like a mismatch right is the number two there are two elements greater than or equal to two in the input array so yes two is the correct answer is the number three would that work as well there are two numbers greater than or equal to three so again there's a mismatch notice that there's only going to be one possible special number and I kind of just went over a little bit of the intuition of why that is you might not have caught it so let me rewind that let me replay what I just said notice how like we have a range of elements that we're trying first of all the solution set has to be in the range 1 through n where n is the size of the input array because there has to be that many elements greater than or equal to whatever element we end up picking right so the solution set has to be in this range we can't have zero because we are given a non-empty array I believe yeah we're given a non-empty array so I guess the only way zero would work is if it's an empty array so we don't have to worry about that if we tried some arbitrary number X it doesn't work either there's too many numbers like there are more numbers greater than x or there are too few numbers greater than x Suppose there are more numbers like let's say there's x + one elements that are actually greater than x okay so then we increment X now we try x + one either there's going to be an equal number or there's going to be too few as we increase X the number that we're trying we're basically shortening this range of numbers we're potentially removing numbers okay but I'm kind of jumping the gun here this is kind of the intuition for the linear time solution so let's hold off on this even though this is quite useful for even solving the solution I'm about to show you right now the easiest approach to solve this problem is to First consider sorting the array because even if you didn't know this fact down here you don't know that the solution set is in this range you 100% know that the solu solution set is going to be either one of the elements in the input array or it's going to be one of the elements in between let me show you why that is suppose we're given an input array like this it might not be sorted when we're given it but we're going to go ahead and sort it that's going to take and log in time that's going to be the bottleneck so now we're going to think of it like this we're looking for elements like X like we want to try X and we want to see how many elements are greater than or equal to X so let's just Brute Force this now that we've sorted the array we can kind of Brute Force this problem what we're going to first try is we're going to have our pointer over here let's call it an i pointer and we're going to say the total number of elements that are equal to this number or to the right of that number are n the length of the input now it could be possible that this number itself is equal to the length of the input right now it's obviously not the length is four this is one but an example could be 4 5 6 7 in that case four is obviously the special number there are four elements greater than or equal to four so we would return four in this case that's not true okay so then we try the next position we try two okay how many elements are greater than or equal to two three elements so again there's a mismatch but it seems like we're kind of getting closer right next we try this element over here four well there are two elements greater than or equal to four then we're going to try the last one and there's only one element greater than or equal to five again that's a mismatch so in this example actually the answer is Nega 1 because we actually didn't find a special number but I want to show you that the algorithm that we just did is not complete just checking each element is not enough it could be possible that the solution doesn't actually exist in the input array it could be in one of the gaps suppose I change this input array suppose I change it by adding a six over here now if we retry it you'll again find that this one doesn't work this one doesn't work and then we get to four it also doesn't work there's three elements greater than or equal to four but we kind of skipped something didn't we we skipped elements in this range we skipped the three three does not exist in the input array but in this example three is the correct solution there are three elements greater than or equal to three so how do we check that well the really really Brute Force way would be to try every number in between these sometimes though that's going to be very large like there could be multiple numbers in this Gap we don't want to necessarily try every single one of them that would make the time complexity worse than the size of the input a little shortcut we can take is this we know at this point there are three elements like to the right here we're keeping track of how many elements are to the the right of our pointer our pointer is right over here and there are three elements so what we want to try is we already know we tried one we already know we tried two it didn't work we already know we tried four as well we didn't try the number in between here we know there are three elements I'm repeating myself a lot there are three elements here and why not try that let's check is three in between the previous number and the current number in this case it is so that's why we would return three let me quickly walk through one last example to really make it 100% clear why this works I'm going to have 1 5 6 78 just to kind of get around the edge case when we start here we know we don't have a previous element so instead of checking like the previous index which could be out of bounds I'm going to have a separate variable which I'm going to call previous I'm initially going to set it to negative 1 because we know that negative 1 is never going to exist in this input so it's a good value to check now we're going to see okay we're at this pointer there are five elements greater than equal to that but 1 is not equal to 5 okay then we're going to check is five in between the previous number and this number nope okay so then we're going to continue we're going to try the next spot we're here there are four elements greater than or equal to five but that's not equal to five so that's not the solution now we're going to check for the number of elements here is that in between the previous number which uh we're going to reassign to be one now and the current number it is so that's where we found our result we would return four this is the solution this is the n log n solution you can kind of see it uses very very similar logic to what I showed earlier where the solution set we know for sure is going to be in the range of 1 through n because we're pretty much trying every single possibility here we're trying n here we're trying n minus one here we're trying n minus 2 etc etc we're going to use this logic to even improve our current solution even more in just a few minutes okay so I'm going to start our pointer at zero I'm going to call Pre previous to initially be1 for reasons I mentioned earlier I'm going to set another variable I'm going to call it total right we technically don't need this variable we could compute it like using our ey pointer but I'm just going to use it just to make things a little bit more readable so initially this is going to be set to the length of nums because we're at the beginning so the number that's total to the right including the index is going to be the length of nums of course so now I'm going to say while our pointer is in bounds let's iterate let's say if the current number is equal to Total right then we've pretty much found our result right so then we can just say return total right or you could just return the current number but I'm actually specifically doing this because we know there's another condition we know that either this is true or total right is in between the current number and the previous number like this in Python you can actually do a full like inequality thing like this with both of these operators so we can check this at the same time in that case we would also return total right okay I actually just realized that we did forget to sort the input so let's do that up here so before we get started with anything let's make sure we sort the input array now I actually want to mention there is something I forgot to say in the drawing explanation there is the case where we could have duplicates for example let's consider a really really simple example let's say we have four occurrences of the number three we are relying on this variable a lot total right when we're here we say there are four numbers greater than or equal to three isn't that correct so obviously this number is three but there are four numbers greater than or equal to it so there's a mismatch but then when we try the second one here we see there are three numbers greater than or equal to this and that is equal to three our a solution that I kind of showed earlier would return three as the special number but we know that's not correct because there are actually four numbers greater than or equal to three in other words we probably want to stick with the first occurrence of each number so if we had an array like two two and then a bunch of Threes we want to like start here and then we want to go here we don't want to visit this one and when we're done with this we don't want to visit these either because we are relying on like this total right I guess a better name for it would be like total that are greater than or equal to the number but that's a very long variable name so for that reason instead of doing our solution like the naive way if we were doing it the way I showed earlier what we would do is first of all update previous so set it to nums of I we would then increment our I pointer by one and we would update total right by setting it to the length of the input minus I this just tells us like how many elements are at index I or to the right of it just this is just the calculation for it there's one more step we're going to do before all this and that is we want to check while nums of I is equal to the next one that's when we want to increment so in that case we want to increment this by one we're always going to increment by at least one so what this Loop is actually doing is given like this array that we were looking at earlier if we were at three right now we would say okay the next one is the same so jump over here okay next one is the same so jump over here next one is the same so jump here so this Loop is going to bring us to the last occurrence of a number if we had a single two for example we're just at two we'd see the next one is three so let's just stay here so this Loop will take us to the last occurrence of a character and then we'll increment by one more to bring us to the next new number so that's kind of the logic and reasoning behind this approach and of course if we don't find the result down here let's just go ahead and return -1 but one thing I guess I did forget is what if I + 1 is out of bounds so in this Loop let's make sure that i+1 doesn't go out of bounds let's just check I +1 is less than the length of nums and this second thing is also true so now we're done with this I'll run the code and as you can see on the left it works well it's somewhat efficient but there is a more efficient approach let me show you that now so this sorting based approach implicitly relies on the fact that the solution lies between 1 through n where n is the size of the array now let's explicitly use that fact to our advantage and we don't even need to sort the input array let me show you what I mean let's kind of reverse engineer the solution I just showed you when we first started at the beginning of the array we were considering this like that's how much total right was so we want to know is n the solution remember our solution set is 1 through n we want to ask is n the solution how do we know if n is the solution well of course how many values are greater than our equal to n in the input array can't we just go through the input array and literally count how many values are greater than or equal to n in this case let's be very concrete the range is 1 through 5 right so I'm going to make a little table over here and for five I'm going to ask how many values are greater than or equal to five it looks like there's only two values greater than or equal to 5 okay so now I want to ask what about four four might be the solution how many values are greater than or equal to four well brute forcing it that's what we got to do cuz we don't know how to use our brains we're going to brute force it we're going to once again scan through this entire input array four five 6 okay there's three values greater than or equal to four that's a mismatch right okay let's try three how many values are greater than or equal to three 1 2 3 okay there's three values okay now we found it like this is obviously the solution right but I'm just going to keep going cuz I want you to figure this out yourself what about two let's go through this let's iterate over the entire input array 1 2 3 4 okay so then four here what about one one 2 3 4 5 right you get the idea is there a way you tell me to eliminate that repeated work how come the values are going in increasing order in this direction is that a coincidence it doesn't look like a coincidence to me it looks to me that the only time we need to iterate over the entire thing is to calculate this position I'm going to redo what I just showed you the more efficient way now I'm going to say that okay let's go over the entire input array count how many values are greater than or equal to five we counted two now instead of counting values greater than or equal to four we already counted the values that are greater than four we literally did that down here that's what we did when we counted five or greater so here we just need to count how many values are equal to four so so we can explicitly Loop for that and we'll see okay there's just one and then here we can do the same thing Loop over the entire thing count how many values are equal to three there are zero but my argument is why do we need to do this this this and this in a separate Loop if we're just counting the occurrences of each number we can do that in a single Loop obviously right so that's exactly what we're going to do here we're going to say okay there's a single two here there's a single one so how does this information help us though well it kind of is like a pre Prix array I haven't drawn it like that sorry the way I drew it is obviously like top down but it's kind of like a reverse prefix array for example if we want to know how many values are greater than or equal to five we get this number here if we want to know how many values are greater than or equal to four we sum up both of these numbers how many values are greater than or equal to three we sum up these three numbers two sum up these and for one sum up these so now if we can build something like this we can just iterate over it in reverse RSE order and try everything like basically if we iterate over these orange values in reverse order we can build these values in linear time and the way I mentioned it earlier was two Loops right I said we can do it with two Loops one Loop to compute how many values are greater than or equal to five and another loop to compute the counts of each of these numbers but there is a way to obviously condense that into a single Loop because what we can say is anytime we see a number that is greater than or equal to 5 put the count here anytime we see a number that's less than five then just count that number explicitly like count 3es count twos count ones but for the largest number which is going to be n in our case just check any number that is greater than or equal to that number and then count it here so obviously this is a linear time solution and linear space solution so let's code it up okay so what I'm going to do is basically what I showed earlier instead of using like a map I'm just going to use a one-dimensional array it's going to initially just be called count it's going to be of length length of nums plus one because uh like I showed we're not going to use the zero index we're going to use indexes from one through n or from one through the length of nums those are the indexes that we actually care about so now is the portion where we're going to do the counting for n in nums let's say we want to ultimately count we want to count n right we want to say count of this number plus one but we know there is a particular case if n is greater than or equal to the length of nums then we're going to get an out of bounds index error so in that case we just want to go to the largest index so the way I'm going to do this is I'm going to call this actually index and here I'm going to have a little if statement a little turn AR operator index is equal to n if n is less than the length of the input otherwise it's going to be equal to the length of nums because we we don't want it to overflow and any number that is greater than or equal to the length of nums is going to go in the last index if you want to condense this you can actually I think just set this to minimum of n as well as length of nums I'm pretty sure this is doing the exact same thing so I'll leave it as is though just to be a bit more explicit but now let's do the same thing I'm going to use the same variable name I'm going to call it total right but maybe there's a better name for it and then I'm going to iterate over this array in reverse order so I'm going to say for I in range we want to go in reverse so I'm goingon to say from length of nums minus one and then do this in reverse order so this is the way to do it in Python like this is basically going from index length of nums all the way down to zero people don't really like this way of writing it though for some reason people complain whenever I do it this way so we will do it a little bit more readable this is the equivalent in Python we can reverse this range just like this so even though this is length + one we're actually starting at the length and we're going down until zero I think now we're going to do what I said earlier we're going to aggregate how many we have and we're going to basically just get the count of index I and then add that to Total right so this should be renamed that we're going to check is there a mismatch or is there like a match is I equal to Total right cuz if they're both equal the index of like that count as well as the count itself are they equal then we can return the value either total right or I if there's not then we would continue and if we never found the result down here we would return -1 and as you can see this solution works as well and I guess this one is definitely more efficient if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon