Sort Array by Increasing Frequency - Leetcode 1636 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem sort array by increasing frequency it's funny that this is actually very similar to yesterday's problem and I think I mentioned yesterday or maybe the day before that sometimes you want to sort based on a custom key and languages have a different way of providing that python makes it very very easy I think most languages do have a way of providing that though and this problem can most easily be solved by doing exactly this so first let's get into what the problem is asking cuz it's not super trivial so the idea is we're given an array something like this every single one of these numbers has a frequency so one has a frequency or a count of two actually it appears two times in the input array two shows up three times and three shows up a single time so instead of sorting the input based on the values themselves we want to sort each value based on the frequency of that value so we want to do it in ascending order based on the frequency so one is the lowest frequency that we have and three is the only number with that frequency it could have been possible though that we had multiple numbers maybe four shows up and it has a frequency of one and we'll cover that case in just a second but for now let's consider this three will show up first next we have a count of two one has a count of two so one's going to show up in the output array but not only is it going to show up once it's actually going to show up twice because that's how many times it appeared in the input so we don't want to eliminate duplicates or anything like that and lastly two shows up three times so we we will add three occurrences of two in the output and that's exactly what we're going to return now let's get back into that other case though where suppose we had four and it showed up a single time so now we have two numbers with the exact same frequency so the straightforward thing to do would be to sort them in ascending order so we could have two elements here like the rest of the array was going to look the same we're going to have a one twice and then we're going to have two three times sorry I'll draw it down here so now these are the elements that show up a single time so we could have either put them like this or this three and four or we could put them like four and three the annoying thing about this problem is that they actually want us to do it this way they want us to only put them in decreasing order if there are elements with the same frequency so this is kind of the complicated part about this problem one way to solve it sure we could collect all elements with the same frequency it might not just be one group you can imagine that there could have been multiple sections that have elements with the exact same frequency and they could be very very long so what would you do would you individually sort each of these pieces cuz that's going to be in log in multiple times which I'm not even sure honestly what the Big O time complexity of that would be I think it might still be in login but there is a better solution and it's an easier solution to code up so that's the one I'm going to be showing you the idea is this when you call like a built-in sort method on an input array so if we call builtin sort on the input array we can pass in a custom key key so what do you imagine we want to pass in for the key like if we have an element one what is the Precedence that we want to give it well remember we're sorting based on the frequency so of course let's just calculate the frequency of each element kind of like I did over here the best data structure to use is usually a hashmap for that so that's what we're going to do and then we'll have that mapping so then we'll say okay for the key don't sort it based on the element num sort it based on the count of num or the frequency of num that will get us pretty far that would give us an output that looks like this now obviously there is an issue with this output it's this part where there are duplicates it's kind of unpredictable it'll sort it based on the count and if two elements have the same count we don't know if it's going to give us the desired result so in Python the way to do that is by adding like a second thing like if there's a tie with these okay then sort it based on something else and the second key that we could provide is the number itself if we do that of course though when there's a tie it's going to sort them in ascending order can you think of a possible workaround we want to not do it in ascending order we want to do the opposite and that makes you think okay we'll try to reverse it well that's hard to do we'd have to reverse like each individual portion then but the better way would be if it's by default sorting them in ascending order the second key instead of being the original number itself could be the -1 multiplied by that number or just you know in Python it'll just be the negative of that number so for example like the sort key for four would be this it would be first the count of four which is one and then next it would be the negative of it which is -4 the sort key of three would be one because that's the count of one and then the second sort key would be -3 so first this part will be evaluated like this first it's going to look here okay these two numbers have the same frequency there's a tie so now look at the second which is the negative of each number by default it's going to try to sort them in ascending order so it's going to say put -4 first and then put -3 because -4 is of course smaller than -3 so that means that you know what number had this sort key four had that sort key and three had this sort key therefore this one is going to go first four is going to be first and then three is going to be second so this is generally high level how you do it in Python when I say we're going to provide a sort key in Python we can only provide a tupal so we're going to have like the first part of the sort key and then the second part of the sort key in the form of a tupal in languages like Java I think you actually have to do a bit more work your sort key will be a function that takes in two parameters A and B and you'll have to do some kind of comparison between them so in Java you actually have more precise control over how exactly you want to do it it's just I think a bit more verbose which if you're a Java person I don't think I have to probably tell you that but anyways given that we're just first counting the occurrences of each number then doing the sorting we can implement this in N plus n log n time so that's the time complexity and Big O of n for the space complexity up above so the first thing we want to do is get the count of each character I could do that in a hashmap for you I'm going to assume you probably know how to do that portion though and I have various videos covering how to do that so in Python I'm going to take the shortcut of just calling the counter on this so this will basically create a hashmap counting each element and then we want to take this we want to take the input array nums and sort it and then we want to return it again the hard part is how we want to sort it we can provide a custom key and that can be in the form of a function while it has to be in the form of a function so I'm going to Define that function up above actually think we have to do that we could do a Lambda function but I'm going to Define like a separate function just to kind of make it very very clear what's going on we have a function it's called custom sort I guess it'll take in a single parameter and I don't think we have control over that it has to take in a single parameter which is going to be a number from the and we want to sort it based on the count of that number but if there's a tie with the count of the number we have to have it in a very particular order so we're going to have a second key so if there's a tie with this then it'll use the next element and it's not going to be the number itself it's going to be the negative of the number because we want them to be in descending order and so now for the custom key here all you do is pass in the name of the function you don't have to call the function do not call the function it won't work in that case so this will work I'll show it to you you can see here it works it's pretty efficient if you wanted to rewrite this in the form of a Lambda function AKA an inline function you could do something like this it takes in a parameter let's call it n once again and then it'll return a tupal so this is just like a short hand for what I'm doing up above it'll return a tupal I'll just copy and paste this because the content is going to be the same this is equivalent to what I have up above generally people prefer to write it below but I thought the previous solution was probably more easy to translate into other languages even though most languages probably don't have like a tupal but this also works as you can see here this time it was more efficient but that's pretty random if you found this helpful check out n code. before recording this video I was working on adding some animations to the DSA for beginners course we'll be adding like about 100 animations to that over the next few days looking forward to it and hopefully I'll see you soon