Sort the Jumbled Numbers - Leetcode 2191 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problems sort the jumbled numbers another sorting problem but the problem description honestly is kind of confusing I'll be focusing on the example so first of all the idea is we're given a list of numbers like this and we want to sort these numbers but as you can see in the output it's not going to be a traditional sort we're given another array and this one is always going to be of size 10 that's very important because what this means is at this position index zero it means that the number zero maps to the number eight and so over here it means the number nine the digit nine maps to the digit six so you can imagine that that's kind of the case with all of these so if we're given an array that looks like this we can take each number and get the real number that it maps to so if 991 well it's going to be nine maps to six so we can go digit by digit six once again 6 one is going to map to 9 so this is going to be 669 we can do the same with the others so I'll go quickly this one actually is a bit interesting so three maps to zero so this one you can see is going to be 0 07 they probably did that on purpose now I'm starting to think they did this one on purpose as well so if there's leading zeros obviously this number the real number it represents is just going to be seven and we can continue with this I think this is also 07 so both both of these are seven they both evaluate to seven so given these numbers 669 7 and 7 how would you sort them well in ascending order they'd look like this 77 669 but the question becomes well which seven will go first how do we break the tie or maybe it doesn't matter well in this problem it does matter the way we will break that tie is based on the original position of the tie so assume that there are two elements that map to the same element this one is at index one this one is at index 2 since this one shows up first that means it's going to show up first in the output this one showed up second so it's going to show up second in the output now if we wanted to take these and then convert them back into what they originally were we'd get 338 as the first one 38 as the second and then 991 as the third and that is the expected output as you can see up above conceptually the problem isn't crazy there are multiple ways to solve it but you're almost certainly going to need some kind of custom sort implemented right obviously you're going to need to do something to map the original values to what the true values that they actually represent using this mapping there are a couple ways to do that I think it makes more sense to show that in the code so that's what I'm going to do the easiest way would be to convert each of these numbers into a string which should be possible I think in most languages and then once it's a string you can go character by character the reason we're converting it into a string is because it's easier to iterate over a string if you just have a number like this it is possible to iterate over the digits and I'll show you how we can do that actually in the second solution but it's just a bit more difficult to implement involves a bit more math and arithmetic um but getting back to this if we can obviously map each of these to the other we can create a string or just the number itself that this represents which I think was 669 and then we can implement the custom sort by by using the mapped value as like the first key so this is the first key that we will use to sort the numbers but in case there's a tie we will break that tie with a second key which will be the index of each value that we have in the input so if we can sort them and the way I'm going to do it in Python is by taking this input array and creating a new list of pairs where the first pair will be the mapped value I'll just call it mapped for short this is going to be like this in the example the second is going to be the index which of course is just the index that each number shows up in so the reason I'm not including the original value itself is because once we sort these pairs we can then rebuild the sorted array with the original numbers by just taking the index of each pair and then mapping it to the value because we're not sorting the input array we are not modifying the input array we're creating a new array of of pairs sorting that and then getting the original values if it doesn't make sense right now don't worry I think the code will probably clear up your confusion the time complexity of this is going to be bottlenecked by the Sorting which is going to be n log in and additional space I think is O of n so what I'm going to do is iterate over the input nums but I'm going to use enumerate because I do want the index as well as the number itself then I'm going to convert each number to a string so like this and I'm going to go through each character in that number now it's a character we want to convert it to an integer because then we can index the mapping array so then we can do something like this mapping now get the actual digit that this corresponds to now how do we build the final integer you could use like a list I'm going to call it mapped n and you could use a list and this could be converted into a string and then you could append that to this and then you could join all of the strings together together that is a valid way but another way is going to be actually a little bit easier but it does involve a tiny bit of math so watch this I'm going to take mapped n and I'm going to add to it this digit so imagine this digit was six for example right we add six to zero well that's great and then suppose the next digit is six as well obviously if we were to add that digit to mapped in we would get 12 that's not quite what we want right so what I'm going to do is actually we have six before I add the next digit I'm going to multiply this by 10 it's going to be 60 the reason I did that is because it's basically shifting all the digits to the left so that then we have an empty spot for the next digit so right before I have this line I'm going to do this mapped n is going to be multiplied by 10 in the first case mapped n is zero so multiplying it by 10 isn't going to do anything but in the next case it'll turn it into 60 and then we add six to it great now we do the same thing suppose the next digit was nine multiply it by 10 we get this and then add the digit 9 we get this 669 that's the idea behind what I'm doing here it's not like a lot of code but it is a little mathy so wanted to explain it after we're done with that we want to take this number and the index and add it to some list and I'm going to declare that up here it's going to be called Pairs and then right down here I'm going to say pairs do append this pair mapped n and the index I the great thing about python is we don't really need like a custom comparator we don't need to implement that but I'm pretty sure you could implement the same logic in Java it would just take a bit more code but all I'm going to do now is just call pairs. sort it will use this first value in the pair as the sort key if there's a tie it will use the next one so after sorting uh we can then just convert each pair into the original value I think if we really wanted we actually could have just sorted the input array I guess the main reason to not do that is because it's better to not modify the inputs if you don't have to so that's why I'm doing it this way but if you wanted to I guess you could call num. sort and then for the custom key you could probably pass in um the corresponding pair but anyways the easiest way to convert these pairs into the original value is to use list comprehension in Python I cover this on NE code. if you're interested in the python for coding interviews course go through every pair the list of pairs and then to this list here add first of all get the index we want the second value in the pair so the index will be here P at index one and then for that we want the original value so we can say nums of this and that will be the number that we add to this list and that will be what we end up returning not sure what's going on with the syntax highlighting here do I have a bug somewhere that I'm not seeing um I'm going to try running the code oh I did and it's very silly up here actually so we forgot to put the keyword in I'm sorry about that let's try that again but you can see that this code works it's pretty efficient I'll show you another solution that is technically just as efficient and I'm only doing it because I know somebody's going to complain if I don't but it just involves a bit more math so we want to avoid possibly doing that string conversion maybe in another language that you're using it's harder to do this so let's get rid of that line right there and then so instead of going through every character let's say while this number is uh greater than zero or not zero so we could say this but it's equivalent to doing this in Python so what we want to do is pretty much what we were doing before but the way to get a digit from something like n suppose it was a 991 it's harder to get this digit first so the easiest way to do this is to go from right to left so this is the first digit we're going to get how do we get it it's not too bad just take n mod it by 10 and then we get the digit now after we get the digit we probably want to get rid of that so that we just have 99 remaining for the next iteration so immediately I'm going to say take n and set it to n / 10 this is integer division in Python it'll round down which basically will get rid of the ones place okay so now we have the digit what do we do to map n well we definitely don't want to multiply this by 10 because to mapped n um which I'll draw down here it's it's initially zero we want to add the digit that we just got it was one and let's say it maps to 9 so we would add N9 to the output but we don't want to like multiply this by 10 because remember the original thing that we had was 991 we want this to be the first digit and then we want this one which let's say it corresponds to six to be added here and then when we get to this digit we want that to be added here so we're not going to have this what we're going to do is add it to here which we don't really need to do the integer conversion version here we can just say mapping of the digit we want to add it but the next iteration we want to add the digit to the 10 place and the next one we want to add it to the 100's place so what I'm going to do is have a another variable which I'm going to call the base initially it's going to be one and this base is going to be multiplied by the digit every single time so base times the digit and then the base is going to be multiplied by 10 every single time which tells us that the next time we want to look at the 10's place and then multiply it again next time we want to look at the hundred's place so just a little bit of math there and this is pretty much the entire solution believe it or not like that's all you had to change but there actually is a bug and I'm not going to pretend to you that I came up with this by myself I ran this code which I'll run for you right now and we'll see that there is a bug I'll let you try to figure out what the bug is on your own if you want but it doesn't take too long to recognize that it looks like we had zero in the wrong spot it looks like zero is supposed uh it's here index zero should map to 9 therefore it should be in the last spot it should have the highest value but we don't have that handled here why do you think that is well it might look more clear when I say while n is greater than zero we're not handling the case where the number itself is equal to zero and it maps to something else so the easiest way at least in my opinion to handle that is when n is equal to zero let's just say a mapped n will just be whatever its mapping happens to be because this Loop will not execute for that it will consider zero as a zero even if Zer is supposed to map to something else if that's the case though we won't expect this Loop to execute because that'll only happen if N is a single zero I don't think we can have multiple zeros in a number I mean by definition we can't like with the way things are coded maybe if it was a list of strings but anyways that will handle that edge case I believe this code is correct let's run it and you can see it works it's also very efficient the time complexity as you can kind of tell us pretty much the same if you found this helpful check out n code. got a lot of cool things coming and hopefully I'll see you soon