K-th Smallest in Lexicographical Order - Leetcode 440 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today I'll solve the problem ki's smallest in lexor graphical order so similar to yesterday's problem and before we get started I want to mention that while this problem can be solved with the same solution from yesterday's problem that's going to be a linear time algorithm and there is a more efficient approach which is roughly a log base 10 of N squared solution actually so it is definitely much more efficient than this one and it's honestly in my opinion not that difficult to understand it's definitely difficult to come up with but when you draw out the picture like I'm going to it actually makes a lot of sense so let's get into it let's consider this example let's say n is 1361 and K is 400 there's a range of numbers from 1 to n which is this and those numbers are sorted lexor graphically so not by like 1 2 3 but based on like the digit so we'd have something like this actually within this range we'd probably have that and then this and then I think a,1 so basically it's the same way strings are sorted like imagine that this was a string rather than a number now to kind of enumerate all of these we can make a tree that looks like this we have initially nine choices something like this I'm not obviously going to draw all of these and then from here this is kind of the prefix so now all the children here are going to be all of the numbers that start with a one well particularly this level is going to include twod digigit numbers since this is a one-digit number so we'll have 10 11 all the way up until 19 now remember that this is a range of 10 numbers this was nine but we keep going so from here we can then go to 100 100 And1 etc etc 10 and9 notice that the pattern is that this was the prefix every single one of these numbers has the same prefix but the next digit is an added digit and it'll be from 0 to 99 so 10 different digits now we could Traverse through this tree because what we want to do is in this order we want to get the Ki smallest number so we could do this DFS kind of like what we did yesterday and once we get to the 400th number so this is the first number this is the second number and then this is the third number and then we'd you know eventually pop back up and keep going eventually we'd get to the 400th number whatever it is that's what we would return clearly in the worst case this is going to be an O of K algorithm I guess you could say o of n as well in the worst case I mean it depends on the K value now the only possible way that we could optimize this is if we knew somehow from here we knew among these choices which one of them actually has the result which one actually has the 400th number well how could you possibly know that well potentially we could check for this guy how many children does it have that are less than or equal to this how many numbers start with a one that fall within the range how many are there and if that number is less than or equal to 400 including this one I guess then we should probably search this side now if not we just saved ourselves a lot of work we can then ask the same question for this like we don't have to go through that entire tree we kind of eliminated that entire tree and then we'd ask the same question here well we just eliminated four or however many choices like if let's say there were 300 choices here we eliminate all of them we can decrement that from K and then we can say okay well now we're looking for the 100th smallest number starting from this number and then going to the children we'd ask the same question how many values are here and suppose let's say there's 200 values that are less than or equal to that range which I don't think there are but I'm just making this up well then we would know okay well the number is somewhere here and so by doing it this way we are going through the entire level in the worst case so that's 10 that's a constant not a big deal but in this case if that's what we're doing for every single level like now two is going to have 10 children and then we're going to ask the same question for here like which one of these 10 children do we actually want to go down so you can see that the time complexity of this solution is going to be determined by the number of levels in the tree like whatever level the Ki value is on that's the time complexity so so 10 * log base 10 of n now that's assuming that we can determine how many values there are along a path in constant time but it's actually not possible to do that in constant time but the algorithm I'm going to show you like that's the whole complicated part of this like figuring out how exactly to do that and that algorithm runs roughly in log base 10 of end time so just by seeing the time complexity you can kind of imagine how we're going to do it it's also going to be determined by going going down levels then you could take this and multiply by that now you kind of see how I'm getting the log squared and I think there'd also be another constant in here maybe 10 and then you know that doesn't really make a big deal so now let's figure out how exactly we can do that with a concrete example we're going to start at one that's always going to be the lexor graphically smallest number in the range from 1 to n I could have a separate pointer which tells us what position we're at let's call it I I equals 1 we're looking for position 400 I could do that but when I actually code this up I'm just going to decrement K cuz it's easier it's more concise to do it that way but I think for visualization it might make more sense to say okay right now we're at the first number we want to be at the 400th number so basically while I is less than K we're going to continue our algorithm okay so now we're at this point we want to know how many values belong to this entire thing including this value there's a couple ways you could actually think about this one that I initially came up with was thinking of how to calculate just the children of this node and while that works the code ends up a bit more verbose than the other solution so I'll kind of show you the more elegant one it's to think of it in this way we're here right now so if we're at one and we need to get to 400 you could say that we need to take 399 steps we need to take like that many steps in our DFS traversal so that's one step another step etc etc now suppose that this entire tree has including this one 399 values that would mean that starting from here if we take 399 steps we're going to actually end up at this value why is that because this is one value and then we have 398 children so for us to jump to the last child it would take 398 steps on the 39 ninth step we'd be done with this entire tree and then we would land on this guy so thus one elegant way to calculate this is to say well if the total number of values in this entire tree if I take that add it to my current position if that's less than or equal to k then the solution is not within this subtree let me repeat that cuz this is the most important part if it's exactly equal like we kind of showed that example 1+ 399 that would mean that this is the Target so I think that makes sense now what if this was less what if this was instead of 3.99 it was 300 that tells us that there's only 300 in this entire tree thus the 400th number can't possibly be in that tree right so that would mean that well we just eliminated 300 candidates and now we're going to go here we took 300 jumps and now we're here now if was greater suppose the total number of nodes in here was actually exactly 400 or maybe even 450 then it's obvious that the 400th value in lexor graphical order is going to be in this subtree and so in that case we would go down a level which would basically take this number and multiply by 10 so we know that this guy has 10 different children 10 all the way up until 19 so really there's two choices either we go down so here or we move to the right over here if we move down we clearly eliminated everything over here in the tree if we move to the right we eliminated this tree so now we understand that now if you know that you pretty much know most of the problem but we just need to figure out that helper function how exactly do we calculate the number of nodes in that particular subtree well let's try to visualize it we're going to do this level by level so we know that this guy I'm I'm not going to draw all of them so it's going to go from 10 to 19 we know this is 20 we want to count everything in this tree so we can start kind of at the first level it's always going to be a difference of one here like for this guy we either want to keep going or we want to move to the right the right neighbor is always just going to be a plus one from here I think that makes sense at the very least this tree will have one value so we take the difference between these two 2 minus one we get a one great now we want to know how many are in the next level so we take this and multiply it by 10 so we get the smallest value in its level now from here you might just think well okay well this level is going to have 10 and technically it will and then we'll go to the next level we'll go to 100 and this level is actually going to have 100 because consider this like this will go all the way up until 109 but this one will have some children as well 190 all the way up until 199 and everything in this range is basically all of the numbers that start with a one that have three digits and they're are 100 of them and the next level will be a th000 there's many ways to calculate this the elegant way is like this we could actually take the other value like we originally started here and here we could take this guy and also be multiplying it by 10 because notice something here this is going to be 20 and then down here this is going to be 200 and so this way we can just constantly take this value and this value and compute the difference which on this level will give us 10 here it gave us one on this it's going to give us 200 - 100 that's 100 this is a pretty nice elegant way but the main reason we're actually doing it this way is because at some point we might actually not want to include every single value on a particular level and that's about to happen right now so now we're going to get to the interesting part we go here it's going to be 1,000 and up until 1,9 here we're going to go to 1990 up until 1999 but notice something this is 2,000 we're going to try to do 2,000 - 1,000 so we're saying that there's a th000 values on this level I mean technically that's possible but our maximum value is 1361 so most of these are actually going to be invalid in this particular case rather than using 2,000 we'd rather use 1361 so that's exactly what I'm going to do so down here I'm actually going to put 1361 let's just do the calculation to see how it would work right now on this level how many can we include in this range and remember that this value is inclusive so right now we would do 1361 minus 1,000 that's going to give us 361 so what does that mean that there's only 361 values in this range that are less than or equal to this number what would that mean that would mean well from 1,000 up until 1360 because I mean this count counts we're not starting from one we're starting from zero so this is that range but no we're actually allowed to have 1361 as well so basically what I'm getting at that's like a long explanation for saying that we're not actually going to take this number subtract it by that we're actually going to take that number plus one and subtract it by that because that value is inclusive okay so we did it and so now on this level we're going to say there are 300 and 62 the plus one comes from the reason I just kind of talked about so okay and now we're done because now we're going to take this number multiply it by a th000 and we're going to get to 10,000 and we're going to see that okay this number the prefix is already greater than n so at this point we can stop so how many did we count in this sub tree there are 1 + 10 + 100 + 362 long story short that is greater than K so there are enough numbers here for us to have the 400th number so we are going to go down this path we're going to go to 10 now and I'll quickly just go through a little bit of this so if we were here that was the first number in lexor graphical order and we're taking this and going here multiplying it by 10 that's a jump of one so our I can say that we're now at the second position but just because we're here doesn't mean that we're actually going to go down this path now here we're going to make the same Choice should we go down here or should we go to its right neighbor which would be 11 so let me kind of illustrate that a little bit so right now I is at position two alternatively you could decrement okay um but now same question how many values does this sub tree have well we'll take 11 - 10 that's going to give us 1 we'll multiply this by 10 we'll get 100 and then we'll get 11 10 take the difference of these two we will get 10 same thing a th000 and this which is that how many numbers are like here in this side of the tree take these two numbers take the difference between them the reason we're still using this number is because this number is still less than or equal to that if this number ever becomes greater than or equal to that at that point we can probably break out of the loop but the more important thing is that you use this number in that case well this number plus one so here this is 100 as you'd expect and now down here we're going to get to 10,000 and since that's bigger than n we can kind of stop now so we counted this many numbers that start with a 10 that would have been in this tree and if you don't believe me those numbers are 10 and then 100 through 100 9 and then like 100 of those values where we're going to go from like a th000 up until 1,9 and then we do the same thing I think from 10 to 10 19 etc etc so those would be like the 100 category but long story short this is 111 so if you take that and add it to our I position we are going to be less than K so we know that the solution is actually not down this path and we are going to now try this path and I don't believe the solution is going to be there either then we would try like 12 and we kind of keep going to the right until we found the one that had the correct like Cas element then we'd start going down now last question you might have is well what if we get to the last position well first of all if we did get to the last position we'd pretty much know for sure that the child is down there because we can't really move further to the right but those computations I believe will still work out cuz if we have nine and we have 10 take the difference of those it's going to be one take 90 take 100 take the difference of those that's going to be a 10 as you'd expect we'll get to 900 and th000 take the difference it'll be 100 so I do believe the math will be consistent in that case while this might be like an understandable solution it's definitely not easy to come up with and to be honest now that I'm kind of going through it I can see why this is a hard problem it's actually not that easy to understand so let's code this up and I actually changed my mind given the fact that I was explaining this in terms of having like an ey pointer I guess I'll just kind of use that just to be consistent so we're starting at one that's like our smallest number and the position of that element is index one we want to get our ey pointer to be K and at that point we'll return the current number so let's just put that down here so now we're going to say while I of course is less than K let's keep going so what do we want to do either we want to move down or we want to move to the right so let's assume we have a helper function that I'm going to call count and let's say given the current position it's going to give us the count of that entire subtree including the element itself because that's going to tell us how many steps that will'll have to move to be to the right position so if we wanted to move to current equals current plus one if we wanted to move to the right this is how many steps we would have to take now if after taking that many steps so i+ steps we're still less than K or we're exactly equal to K that would mean that current + one is the solution in either of those cases we want to move to the right because either current doesn't have enough children well yeah that that pretty much just means current just doesn't have enough children the Ki element is not going to be on that sub tree so we move to the right otherwise it does have enough and therefore we want to move down the way to move down is to take current and multiply it by 10 now we also want to keep track of our current position if we multiply by 10 that's actually the easiest case in our DFS case that's just taking one step so we can take our ey pointer increment it by one if we move to the right we have to take this many steps to do that so that's exactly what we're going to do increment I by the number of steps now for actually Computing the count which isn't super crazy but I would say it's probably the hardest part of the problem so let's do that give count and let's say current and let's compute the number of steps so I'm going to call that result and that's what we're going to return and so we want Its Right neighbor the current's neighbor so I'm just going to call it that let's say neighbor and I'm going to say current plus one that's initially what's the case and and so remember we want to keep going while our current is less than or equal to the N value that's up there so while that's the case to the result you could say we want to add to it the neighbor minus Kerr and then each time we want to take CER and move down a level so multiply it by 10 and do the same thing with the neighbor multiply it by 10 the only catch is what if the neighbor is actually greater than n then we' be counting too many so one way to do this is to say well neighbor could be equal to the minimum of itself and N but not just n we want to do n plus one for reasons I talked about it makes the calculation work out so this will work obviously you could take this and just substitute it here and do that and then you can get rid of this line so there you go this is the entire solution and it's definitely not easy this is a hard problem for a reason let's run it and as you can see here it works and it's pretty efficient I think if I ran it again it might do better well anyways thanks for watching check out N.O for a lot more and I'll see you soon