hey everyone welcome back to the channel i hope you guys are doing extremely well so today we will be solving the problem k permutation sequence from the sd sheet but before moving on to the problem if you are new to our channel please please please do consider subscribing to our channel so the problem states that you'll be given a value n and you'll be given a value k so if you're given n so the set will be 1 2 3 up till n and you know any set which is containing n numbers is going to contain exactly n permutations exactly n factorial permutations right so just imagine if n is given as 3 so can i say this is going to have three factorial permutations which is six permutations so all the six permutations are written over here if you carefully observe now it does now if k is given as three so you're gonna tell the third permutation which is 2 1 3 if k is given as 5 you're going to tell the fifth permutation so the question is very straightforward you will be given a value n so you know for every n there will be n factorial unique permutations and if you sort them right if you write them in lexicographical order you need to return the kth permutation among all the n factorial permutations so this is the question that you need to solve so obviously if this question comes up in the interview what will be your first approach the first approach should be brute force yes where you tell the interviewer that you're gonna use the recursive way to generate all the permutations right so you can use the recursion so i will not be telling you the recursion code but i'm just telling you the brute force so use recursion to generate all the permutations so once all the permutations are generated so that will be into some data structure so what you need to do is you need to sort this data structure so simply sort this data structure once you have sorted this data structure i can surely say that the kth permutation will be at the k minus 1 index assuming that the data structure is storing all the permutations in the zeroth based indexing order so i can say the k permutation will lie at the k minus 1 at index so this will be the brute force that you're gonna tell the interviewer that you're gonna write a recursive code in most of the cases the interviewer will never ask you to write the recursive code because the recursion is not the solution for this question so he will just ask you what will be the time complexity of recursion and all about that so you're going to tell him that it will be n factorial because you're going to generate all the permutations so the recursion is going to take n factorial time and obviously you're going to make a deep copy of every permutation that you generate to put it into this data structure so the deep copy is going to take a big of n time so the total time of the recursion will be n factorial into n so that will be the time that recursion is taking after that you have to again perform a sort right so if there are n factorial list so it's gonna take n factorial time n factorial log n factorial time to sort so it's gonna take a lot of time to sort so this is what you're gonna tell the interviewer now this is the moment where the interviewer will interrupt you generally and will tell you that this is taking a hell of a time and you need to improve the time complexity and this is where you're gonna jump into your optimal solution right don't jump straight away into the optimal solution because in an interview it's a process you start off with the naive solution then only you move to the optimal solution so when the interview will interrupt and tell you to optimize this that is the moment you present him with the optimal solution so let's discuss the optimal solution now so if n is given as 4 right so we know that there are 24 permutations because that is 4 factorial so there are 24 permutations so if i am looking to find k equal to 17 permutation let's look into this mathematically so i know the set is going to contain the numbers 1 2 3 and 4 okay so if i just pick up the number 1 and i say the other numbers are 2 three and four right so if i say this that means i'm starting the permutation with one now what if i say let's start the permutation with two so i can say the rest of the numbers will be one three four now what if i say let's start the permutation with the number three so the rest of the numbers will be one two four now let's say we're gonna start the permutation with the number four so the rest of the numbers will be one two and three so i can either start the permutation with one or either i can start with two or either i can start with 3 or either i can start with 4 so can i say the number of permutations that will start with 1 will be 6 the number of permutations that will start with 2 will again be 6 the number of permutations that will start with three will be six the number of permutations that will start with four again will be six now why can i say that because these are three numbers and they will permute in themselves so if three numbers do permute in themselves they're gonna take three factorial and that is nothing but equivalent to six so basically six plus six plus six plus six is going to give you 24 unique permutations that is your total number of permutations right so now let's look it into mathematically right so i'm saying that i require 17 right i require 17 so at first let's put all these numbers into some data structure so the data structure will have one at the zeroth index this will be at the first index this will be at the second index this will be at the third index now i can say that i'm gonna mark all the unique permutations in zero based indexing right so if the first permutation is one two three four well the last is four three two one that's the first and last so i'm gonna call it the zeroth permutation while i'll call this the 20th permutation so i'm gonna mark the permutations by zero based indexing numbers so in that way i can say this permutation will be containing zero to five in zero base numbers this is gonna contain six to eleven permutations this is gonna contain 12 to 17 permutations this is going to contain 18 to 23 permutations i can surely say that right so if the question is stating to find the 17 permutation so what i can say is i'm actually looking for the 16th permutation because i have taken everything in zero base indexing so i'll be looking for the 16th permutation instead of looking for the 17 permutation right so ask a simple question if k is 16 in terms of zero based indexing so which will be the first number in your 16 permutation so can i say the first number will be 3 because in this range is where 16th permutation will lie so i can easily see if they're containing six numbers for every range right every range is containing six numbers so 16 by six is nothing but 2 so if i'm considering 0 based indexing so the number at the second is nothing but 3 right 0 1 2. so at the second index i have a number three so i can surely say that my permutation starts with the number three so i have got the number with which my permutation starts so what i can say is since i've got 16 so i can say 12 numbers have been taken because 6 plus 6 12 numbers i have jumped so now i can surely say that my sequence is lying in between this so how many numbers are over here so the number of sequences oh in this range is six and out of these six sequences i actually have to find 16 modulo 6 that is four the fourth sequence out of this six sequence if i'm able to find this i think my job will be done right so let's move into the next step but i'm trying to find the fourth sequence so it did boil down the question you need to understand now the question has been boiled down you just have to figure out which is the fourth sequence among these six sequence so can i say the set of numbers remaining if you have picked up three will be one two four so all the permutations generated among these you just have to figure out which is the fourth permutation sequence among these permutations all right so let's do it so since the question has boiled down to the list of numbers as one to four and finding the fourth permutation among all the permutations generated by this list so let's follow the same process again so if i say my permutation is going to start with 1 i can again say my permutation is going to start with 2 i can again say my permutation is going to start with 4. so if they're starting with this i can see that the rest numbers are 2 4 over here the rest numbers over here are 1 4 while the rest numbers over here are 1 2.
so if there are two numbers can i say this is gonna generate two permutations this is also going to generate two permutations this is also going to generate two permutations which makes a total of six permutation again you know if there are three numbers the total permutation generated will be three factorial that's six so we have figured them out into ranges so i know this is going to be from 0 to 1 the 0th permutation and the first permutation this is from 2 to 3 saying the second permutation and the third permutation this is going to be from 4 to five saying the fourth permutation and the fifth permutation so since k is four can i say since i know every one is having two that everyone is having two permutations let's divide it by two so i can say my permutation will actually lie in this second this is the zeroth one this is the first guy this is the second guy so i can easily say my permutation is gonna start with four right next so i figured out the next number that is four so the permutation is starting with four again it does make sense because the four is lying in the range four to five so if you simply divide it you will get which is the number where it is starting so since i have figured out yes i figured out that 4 is the next number so what will be the value of k left so again you're gonna do a four modulo two so when you do a four modulo two it says zero right that means the question now boils down that you have a set of one comma two right because you have already taken three four and now you have to figure out the zeroth sequence yes the zeroth permutation among all the permutations generated by one two so let's do that so i can say again the same procedure that my permutation is going to start with 1 or my permutation can start with 2. so if a permutation starts with 1 i will be left off with two or if a permutation starts with two i'll be left off with one so this will be one factorial so i can say this will contribute to one permutation this will contribute to one permutation and a total of two permutations again does make sense because if n is 2 i know the number of permutation will be 2 factorial which is nothing but 2 itself so this will be the range zero to zero permutations and this will be the range from first to first permutation so if you're looking for k equal to zero you can simply divide it i know every range is having one so if you divide it by 1 you get it as 0 so since you got 0 you can easily say that this block is the block which will contain your permutation that means the permutation should start with 1 so you can pick that one and you can say that that is your third number now since you have picked up zero right you've picked up the zeroth permutation again you look for the remaining that is zero modulo zero so again you're looking for the zeroth permutation at the next so the next value of k will be zero so can i now say that your list is now containing only two and you're looking for the zero permutation among two yes so if you again follow the same process i can say i will have the permutation starting with two but right now i don't have anything left yes this is the moment you don't have anything left so you don't need to figure out anything just pick out the remaining number and you tell this is going to be my last number and this is how you can easily figure out your permutation without doing recursion so it's very simple guys so this is how you are going to solve this problem so if i summarize this initially you add four right and you know there will be four factorial that has 24 permutations so at first you divided it into six blocks blocks of six and then figured out where does 16 lie so you figured out 16 lies over here then what you did was you did a 16 modulo 6 the remaining number that's four so now out of the six at the next stage you figured out where does the fourth sequence lies in this six so in the next block what happened was you took blocks of two then you took blocks of two and it took blocks of two and out of these you figured out where does this fourth sequence lie and you figured out that the fourth will obviously lie over here because this will be 0 to 1 this will be 2 to 3 and this will be 4 to 5. so did you observe something this was 4 factorial so the next is 3 factorial which is 6 so you're dividing it into six blocks next is two factorial which is two and you divide it into two blocks the next step you did divide it into blocks of size one if you remember so the next was one factorial so basically it's a factorial stuff that you're doing it's just figuring out where does k lie in which block and whichever block it lies you're just picking out that number in itself right you just pick up that number in itself like over here there was 16 so k was 16 by 6 so that that was basically the second block so you figured out the third number is what you're gonna pick up over here k was 2 so the second number was 4.
so you picked up 4 over here k was 0 so the 0th number was 1 so picked up 1 over here again k was 0 and the 0th number was 2 so you picked up 2 so at first three then four then one then two so that's how you're going to pick up so i hope you have understood the mathematical part it's just the implementation part that will be worrying you so i'll be showing you the code so don't worry about that once you see the code you'll have much more clarity about the implementation as well so what is the time complexity so can i say if n is 4 i'm actually looking for the four numbers that will be in your permutations so that's going to take a big o of n for sure because you're looking for four numbers so that's the big of n for sure and remember whenever you picked up three the set did reduce to one to four and then you again splitted them into blocks so you're basically taking this three out the next step you're taking this four out to get this set the next step is taking this one out to get this set so this taking out is taking big off n because even if you use erase functions it is functions do take a big of n time if you are wanting to erase any middle element so the time complexity will be big o of n square and the space complexity will be big o of n again because you're using this vector and also you have to store this answer right you have to store this answer that you will be returning so the space complexity will be big o of n so this will be the time complexity and space complexity now it's time to discuss the c plus plus as well as the java code so let's discuss the c plus plus code so what we can see is you're given the n and you're given the k and if you return a string which will be the kth permutation for the given value n so what did we require initially we required something as three factorial because we know the first division was in terms of blocks and we also required a array which will be having all the numbers so that is what we do over here we compute factorial 3 if n is 4 that means n minus 1 factorial is computed and all the numbers from 1 to n are being stored if you take this line into account so initially we compute three factorial or n minus one factorial and we store all the numbers in the array so this step is done and you have computed six right what is the next step you know if k is 17 now since our logic will be running on zero based indexing so let's reduce k by a value one so we reduce k by a value one so k becomes k minus one and you are initializing a string with empty so that it can store your ultimate answer that's 3 4 1 2 right at the beginning what did we do we know we will have blocks of size six right everyone knows we are gonna have a block of size six so what we do is we basically make sure that sixteen by six is done so whatever is the number two so let's pick the number over here that's 3 so that is what we do over here just pick that number convert it into a character that is 3 and add it to our answer so 3 gets added to your answer right after that you need to decrease you need to erase three so that is what we do over here we it is three and k by factorial that means k is 16 and factorial is six as of now so that is done now once this is done you're going to keep on doing this unless and until your list this 2 is taken and at the next step your list becomes empty you're going to keep on doing this so we keep on doing this what will be the next value of k obviously it's going to be 16 modulo 6 that's 4 that's going to be the next value of k so that is what we do k equal to k modulo fact what will be the next factorial the next time the blocks will be of size 2 isn't it 1 factorial less so that's that's what you do just divide it by the size because the size now will be three so if you're looking for two factorial just divide six by three and you'll get the two factorial so this is what will be going on for every step you can keep on doing this till you haven't picked up every number from this array once you've picked up every number from this array you will have your answer string stored as 3412 which you can return as an answer so this will be your c plus plus code so let's discuss the java solution for this problem so initially you're given n and k for which you have to find the k permutation and they are wanting you to return a string which should be having the kth permutation so initially what we do is we take a variable factorial and we compute n minus 1 factorial y because you know if k n was 4 so the first block was of a size 6. so that's nothing but n minus 1 factorial so the first block will be of size 6 so that is what we compute and we're also making this array of size 4 which is going to store all the numbers 1 2 3 4 so we store all the numbers from 1 2 3 and then the 4 over here so all the numbers are stored now we need to return the answer in a string so we declare a string array which is empty right after that we are subtracting k by 1 because in our logic we are considering zero based indexing logic to solve so if they're asking us to find 17 permutation right so we will be finding the 16 permutation that's why i reduce the value of k by 1 to make it 16 right after that we are going to run an infinite loop l when l this doesn't becomes 0 because at the last step when you pick up two the list will be empty at the last step so you're gonna keep on doing till the list is not empty right so that's why i run a true loop so basically the next step what you do you're basically considering k by factorial what's k that's 16 16 by 6 is 2 and you know this is your first number of your permutation so basically pick out the second index number which is 3.
