Lexicographical Numbers - Leetcode 386 - Python

Key Takeaways

hey everyone welcome back and let's write some more unat code today so today let's solve the problem lexor graphical numbers the idea is that we're given a range one through n which is defined by the only parameter that we're given which is n so the range always starts at one let's consider the example where we have something like 136 the idea is that we want the numbers to be sorted not by like the integer values like that would be 1 2 3 4 5 in increasing order but we want them to be sorted by like the digits the same way we would have some strings let's say a b c and then a c b this string would go after this one because there's a tie in the first position but when you compare the first differing characters B is less than C therefore this string is smaller it's going to go first if you had two strings that were of different lengths like this entire string matches that one the first differing character is this one this one is empty this one has a c so this one would be first AB would go and then we'd get a b c so the same idea is going to be applied to these numbers in other words the first digit is going to have the most precedence so think of it in terms of this we have this range of numbers we want first to get all the numbers that start with one there's not going to be any leading zeros but we want all the numbers that start with one after we get all of them then we want all the numbers that start with two and then all the numbers that start with three Etc Etc from this perspective we've gotten to a sub problem here we're at one now for the remaining digits that's what we're choosing here we're choosing the remaining digits so we could get 10 we could get 11 all the way up until 19 notice that the difference here the first choice we had decisions 1 through n the next choice here we have 10 decisions well I guess you could say 0 through n for the second digit we have those choices now as we go like I said this is technically smaller than all of its descendants because it has the matching prefix with all of them but all of its descendants have a greater lengths so clearly this one is going to go first and then all of its children and all of its children are going to go from left to right but there's a catch what about the children of the children what about 10 it has some children doesn't it we do the same thing add another digit and by doing that we're basically multiplying this by 10 we get 100 then here 101 all the way up until 109 so here the sub problem becomes get all the numbers that start with 10 and we know for sure that this guy and all of its descendants are going to go before its neighbor over here so we do this recursively that's the whole idea behind this problem now how do you know when to stop well eventually we're going to take this and multiply it by 10 let's say we get to a th000 clearly that's too big we know we can stop because it exceeded the max number we don't really have to go through those guys either and same thing like none of these are going to have children either but then we're going to come back up to 11 and then we're going to eventually do 12 and eventually we're going to get to 13 and it's going to have some children 130 all the way up until 139 well not quite we're actually going to end up stopping at 136 cuz that's the max number there's no point in going to 137 or greater so that's another reason for us to stop where we exactly reach the number itself and so basically this is a backtracking solution where we're doing DFS in a preorder fashion because every time we get to a value we're going to immediately add that to the result and then we're going to go here add it to the result then here add it to the result do all of these pop back up do this do all of its descendants etc etc and then we're going to pop back up to here and then pop back up here I guess but two while it will have some descendants it will go up until 20 but we won't get into to the hundred's place we won't have a 200 or anything like that and we'll kind of keep going we'll do the same thing for this node as well and I think we'll actually get it up until 9 and then the max number from there will be 99 I guess in this range the largest number lexor graphically is going to be 99 the problem with this solution obviously it does use some extra memory given that it's recursive but it's not a lot of memory like the height of this tree is going to actually be log base 10 of the max number because each time we go down a level we're multiplying by 10 so how many times can you multiply by 10 until you reach this number or how many times can you divide this number by 10 until you reach one those are both equivalent those can both be determined by the log function so that's the space complexity time complexity is linear as you can see each number is only going to be visited a single time so while we don't meet the constraints I will show you the solution that does in just a minute but first let's code up this one so what I'm going to do is declare the result and that's what we're going to return all the numbers in the form of a list and then I'm going to create our recursive function I'll call it DFS and we'll have a current value and we know that the base case is going to be when the current number exceeds n if it equals n we're not going to return because if it equals n we do still want to append it to the result so we'll do that here in pre-order fashion and then we're going to go to the descendants of the current number and that's not going to be a simple recursive call that's actually going to involve a loop we're going to say for I in range 10 cuz we want to go from 0 to 9 we're going to do this DFS on the current number multiply it by 10 and then add I if any of those exceed n the recursive base case will hit and then will return immediately anyway so while you could have like an if statement here you could also early Stop the Loop it doesn't really make that much of a difference if this is more readable written this way for you feel free to do that current uh multiplied by by 10 and then to the new current value just add I so that way we don't have to keep doing the multiplication by 10 each time the problem here is that we can't just easily call DFS starting from one because if we do that this recursive call is only going to give us all the numbers that start with a one but some numbers might start with a two or three or four how do we get those well you can't also start at zero either because the way this is written then we would have a leading zero in our result and actually I think we'd even get infinite recursion cuz we would try multiplying that by 10 it'll still be zero and then we'd add zero to it and then we'd probably get infinite recursion so the better thing to do here is a loop so for I in range the starting value is going to be from 1 through 9 so we write 1 through 10 in Python this is non-inclusive and then we do DFS starting from I there you go I believe this is the entire code let's just run it and it works and it's pretty efficient in terms of time complexity but the runtime suffers mainly because of the recursion like the overhead introduced by all these recursive calls and the space complexity definitely suffers as well so how exactly can we optimize this well the obvious way to take a recursive algorithm and make it iterative is to use a stack data structure well yeah that'll technically work but it's not going to reduce the memory because from 100 down here we'd still have to remember to pop back up to 10 and then from 10 we'd still have to remember to pop back up to one but do we really need to remember that is there a pattern that you notice from all of these to pop back up to the previous level and even if we were to have drawn it from here what's the pattern it looks like all we do is remove the last digit because from 10 we added the digit zero here we added the digit one here we added the digit there to reverse that we can just divide it by 10 integer division so that we round down but it's really that simple so conceptually now we know how we can get rid of the need for a stack and we can optimize the space to constant space but it's not quite that simple cuz with recursion sometimes you don't just pop back up once you continuously pop back up when would that occur well it definitely wouldn't occur from over here because when we pop back up to 10 then we're going to go to 11 and then 12 etc etc but on the last value in that level then we would want to pop back up multiple times let's consider the example where the n value is actually something like 100 or1 19.99 from here eventually we'd get down to$ 19.99 that's the last value so we know we can stop we divide by 10 to pop back up here just to make it more simple consider it from this side when we pop back up here on the last level let's say from 109 we pop back up to 10 we don't want to revisit the same value we want to go to the next value so what we would do after popping up is we'd add one to it cuz we're doing pre-order traversal we don't want to add this guy twice so we add one immediately after popping back up but that is sometimes going to cause an issue cuz right now from here if we pop back up and we add one to this we're going to get to 200 that's not quite what we wanted cuz we haven't even visited two yet and we haven't even visited 20 yet so why would we want to visit 200 first so that's the issue here we don't want to add one to this we want to pop it again and from 19 we don't want to add one to that that would give us 20 we haven't even visited two yet so we don't want to do that we want to pop back up again what's the pattern why are we popping up multiple times because we reached the last number in the level here and here how do we know we reach the last number in the level because the last digit is a nine how do we get that last digit that's pretty easy you just mod it by 10 so if that's the case we would keep popping back up so we don't need an if statement to pop back up we actually need a loop to continuously do that I think that's probably the hardest part about the iterative solution and the other thing is um imagine that we reached this number like down here we reached 136 we know that we pop back up not because the last digit is nine but because this number is actually equal to this one that's another reason to pop back up so that's more or less how you do the iterative solution so let's code it up now I'm going to leave this code here we are still going to have a result we are still going to return it and we're going to do something slightly differently we're going to do this iteratively so I'm going to use a loop I'm going to say while the length of my output is less than n I'm going to keep going we're going to start at one so we can put that here current is one the easiest thing to do is just to take the number every time we expect the current number to be distinct and to continuously follow that iterative sequence so every time we have that number we're just going to add it to the result like this now just like in the recursive solution where we multiply by 10 make the recursive call and then from that recursive call we do the same thing check the base case multiply by 10 make the recursive call we're basically multiplying it by 10 as much as we possibly can that's the first thing that takes the highest precedence so if current times 10 we don't have the luxury of a base case so before we actually multiply it by 10 let's check that it's in bounds let's check that this multiplied by 10 is less than or equal to n if so then do that perform that multiplication and then on the next iteration of the loop we're going to add it to the result and we're going to keep doing this as much as we can now if that's not the case we have to do something different okay we can't multiply it by 10 so there's two things either we pop back up or we add one to it well remember after popping back up we're going to be adding one to it anyway so we might as well put that here we might as well add one to it now this is the optional part we don't know if we're popping back up how do we know if we would be popping well if current is equal to n it's already as big as we can possibly make it so we better pop back up before we add one to it because we don't want a number larger than n to be appended to the result so that's one case or obviously if the number moded by 10 is equal to 9 if the last digit is a nine if we add one to it that's not going to give us exactly what we want so that's another reason to pop back up when I say pop back up I basically mean take the number and integer divide it by 10 and so this is not going to be an if statement remember it's going to be a loop but that's pretty much the entire solution I'll go ahead and run it and as you can see it works and is more efficient thanks for watching if you're preparing for coding interviews check out NE code. I'll see you soon