Permutation Sequence | Leetcode #60
Vložit
- čas přidán 19. 06. 2020
- This video explains an important programming interview problem which is to find the Kth permutation of a string of length N. In this problem, we are given number of digits N and Kth permutation to be found K.We can simply generate the permutations from the beginning and find Kth permutation.But this method will take a lot of time which is O(N!).This is not feasible.We can apply some mathematical intuition to solve this problem in just O(1).I have shown the intuition and method for solving this problem in the most efficient way.I have explained the algorithm with proper examples and at the end of the video, i have shown the code walk through.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
SIMILAR PROBLEMS:-
String Permutation Algorithm: • String permutation alg...
I live for the day I can come with solutions like this myself. Kudos man and thanks for making these videos
😅 Man you will do it in some time.
Just keep practicing and you will do it! But don't just watch the video to know the answer, try as hard as possible to figure it out yourself, and then when you're ABSOLUTELY stuck then watch the video
You got it brother
I searched the question on youtube, found many popular CZcamsrs with the explanation video. But my heart knew which video to land on!!
😂
You did a great job of explaining the algorithm.
I just watched the first part, it gave me suggestions about how to proceed with my own solution. Thx
Very good :)
Absolute Gold. Thank you sir !!
Welcome :)
Thanks! I am aware of the process but didn't implement it successfully, probably due to the -1 for boundary. The implementation logic is pretty smooth.
Welcome :)
what tool/device you use to make this video? looks good
use index =(k-1)/fact[n-1] to get rid of the boundary case
Please tell the name of software that you used for code explanation
TECH DOSE, Can you do a video on "Next permutation sequence", I think it's along the same lines as this problem
the clearest explanation ive ever seen for this question. love u.
Thanks 😊
If index is re-written as "index = (k-1)/(n-1)!".. you can avoid extra checks for boundary values of k.
Good explanation! One trick to handle the boundary case is doing "INDEX = (k - 1)/(n - 1)!" instead, then you don't need to explicitly check for the boundary condition :)
👍
k - 1 may go to a negative value which leads to an exception in Rust.
this tutorial is very helpful.
but i am facing some issues.
..
when the digit is [0 - 9]
and the k = 1000000.
the index value i got is 27.
but our digits are 1 - 10.
..
can you please explain me ?
I'm not that good with maths but I'm glad that I was able to solve this problem on my own :) Tho my code was messy.
Just came here for better code
I was stuck in the index-- part when it will be a multiple of block size. Took too much time in that boundary case :(
@@techdose4u I missed one corner case too.
I have a more simpler solution using stl
@@maythecodesbewithyou29 Can't use that in your interviews tho.
how to get the kth permutation of the repeated letters ?
sir can you make video on valid permutations of DI sequence leetcode (dp,hard)
Can someone provide the solution of the brute force algo
Sir, thanks for this video..Helped a lot ...Sir can u tell me the software u use for screen and audio recording..? Thanks :)
Techsmith camtasia and Audacity.
you can use quicktime for recording screen and recforge ii for recording audio
@@maythecodesbewithyou29 okay thanks :)
this is O(n2) right. since removing a middle element from array itself O(n)
Correct
You can make use of Doubly LinkedList instead of an array
here max size of array will be 9 only, so it doesn't affect that much.
Yes. But N is only 9 😅
I have observed, most of the questions on leetcode are from mathematics of class 12th
Thank you,
Sir, you are the best how do you think such an amazing approach I REALLY WONDER Please sir tell me what are your strengths?
Keep practicing bro. That's the only key. There is no easy or shortcut way.
can this question will be asked in interview ever, as this is very difficult to understand ...
I am preparing for internships, does this level of questions are asked in interviews ? please reply....
Chances are low.
Superb Explanation! But just a request, could you go a little slow in your explanations and dry run, since u keep changing tabs & do the calculations quickly , we loose track. Thanks for these vids!
This was a tricky problem and solution parts were separated in tabs. That's why I asked to write on paper and try. You can pause the video and dry run after watching the video once. This way you can cover all parts.
how the number of blocks is 2? [123,132] [231,213] [312,321] so the number of blocks is 3 only ryt?
how do u know/find what's the block size??
Map
Genius!
😅
Thanks a lot
Welcome :)
in case k % (n-1)! == 0, you dont need a special statement for this.
index can be calculate by (k-1) / (n-1)!
thank you
Welcome
Please make videos on subsets I and subsets II sir.
Sure
This problem would be complex if characters/numbers could repeat.
Good tutorial bro but how can someone come up with this soln in a 30 min interview given that he have never seen such type of problem before
If you are asked and you can give the ideas about block access then you will pass. You don't have to cover the boundary cases or give the exact formula. Generally DS & algo based questions are asked and not math based. This comes in CP generally.
@@techdose4u yes you are right
Bhiya do these type of mathmetical question are asked
It is not asked but may come in coding round.
Out Of My Syllabus!
😅
June challenge is very tough
Good for learning :) I hope they will close the challenges. That's why they are ending it with tougher problems :)
it should be fact[n-2].
5/2+1 is wrong rather it should have been (5+1)/2
Don't you sleep bhaiya?
Gna sleep now. This daily videos are making me sick 😅 Just 10 more days :)
EDIT: This goes for you too 😂
Yeah these daily videos are making me sick as well , have to wake up till it's posted 😂
I thought you wokeup just now 😂
It's the other way around 😂
@@techdose4u
Tech Dose: Just 10 more days!!!
July Challenge: I am coming 😂😂😂
Applying backtracking in this is waste of time 😛
😅
you change your tabs alot...kindly avoid that as it creates disturbance
You mean the video cuts? I try to reduce redundancy in explanation.
@@techdose4u NO, i mean while explaining the concept you change the slides a lot of times...this makes a lot difficult to understand the concept..Like in this slide you were going back and forth a lot of times...please avoid it