L18. K-th Permutation Sequence | Leetcode

Подписаться 623 тыс.

Просмотров 191 тыс.

50% 1

Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem Link: leetcode.com/problems/permuta...
C++/Java Code: takeuforward.org/data-structu...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements

Опубликовано:

28 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 283

@takeUforward 3 года назад

Please leave a small comment if you understand by spending your time here, every comment motivates me more :) C++ Code: github.com/striver79/SDESheet/blob/main/permutationSequenceCpp Java Code: github.com/striver79/SDESheet/blob/main/permutationSequenceJava Instagram(For live sessions): instagram.com/striver_79/

@kajalKumari-yd9tj 2 года назад

this code is not working for a test case on interview bit ru-vid.com/show-UCz9dtkYt27fb2priOSu_3dw public class Solution { public ArrayList findPerm(int A, Long B) { Long fact = 1L; List numbers = new ArrayList(); ArrayList ans = new ArrayList(); for(int i = 1;i

@shauryavatsa595 10 месяцев назад

It was unimaginable that i could ever learn DSA, but then i found you. Thanks a lot.

@aakstatic 3 года назад

This series is so underrated! It deserves a lot more views. Thanks to Striver for doing this noble work. :)

@divyareddy7622 2 года назад

why is it 16%6 at 9:23

@harshkedia6493 2 года назад

@@divyareddy7622 bcz he had divide them in group of 6 and he is taking 0 based indexing so 6+6+4 that is k th number hence 16/6=2 and 16%6=4 so (2*6+4)=16(kth number) .

@Zunan263 2 года назад

Actually 💯

@nopecharon 2 года назад

It's not underrated

@lakshsinghania 11 месяцев назад

watched it 2 times to get the concept

@samratpodder545 2 года назад

Thanks Striver, for sharing the pick / not-pick thought process and the clear demonstration of backtracking. This playlist is equally awesome for beginners as well as experienced DSAers. Recursion is now a lot clearer. Will be starting with the DP Playlist very soon !!

@YashHalgaonkar 2 года назад

Much clear and conceptual code: string getPermutation(int n, int k) { int fact = 1; string res = ""; vector arr; for(int i = 1; i 0) { fact = fact/arr.size(); res += to_string(arr[k/fact]); arr.erase(arr.begin() + k/fact); k = k%fact; } return res; }

@freecoder522 2 года назад

can I get the complete code

@YashHalgaonkar 2 года назад

@@freecoder522 its complete.

@freecoder522 2 года назад

complete working code : #include using namespace std; string getPermutation(int n, int k) { int fact = 1; string res = ""; vector arr; for(int i = 1; i 0) { fact = fact/arr.size(); res += to_string(arr[k/fact]); arr.erase(arr.begin() + k/fact); k = k%fact; } return res; } int main() { int n = 3, k = 4; string kthsequence = getPermutation(n, k); cout

@ghj7275 2 года назад

Completed the entire playlist and let me tell you, this is the best one out there. There are so many questions that I couldn't solve an year before but now I'm able to after watching this series❤❤❤

@harshtewari4333 Год назад

Same

@atharvakalele37 2 года назад

This was a tough problem to grasp but u made us do anyway...u r awesome dude!

@lakshsinghania 11 месяцев назад

indeed it was

@adityamaheshwari3046 2 года назад

13:28 , 20:16 - Just a suggestion, as soon as we see the value of k is zero we can break/end recursion right there and append the remaining string into the answer. Intution is that k=0 means we have to find the first smallest permutation and first smallest permutation is the number itself (since our input string is already sorted)

@atjhamit 2 года назад

Works for the current scenario but not a good practice to introduce if statements for edge cases. Ideally the lesser the number of conditions, the better(code readability and other such standards).

@lakshyaagarwal5301 5 месяцев назад

Have tried that on gfg and leetcode, it doesn't satisfy the time complexity. Think about the worst case scenario what if n=9 and k=9! i.e the required string is the last possible permutation It would take a lot of time. I know how it feels don't worry i have been there 🥲

@anishali8042 Год назад

Please pin this comment! 8:52 Why 16%6? It is because there are 4 groups defined and in one of the 4 groups, the kth permutation will lie. 1, (2,3,4) Group 1

@saranshpathak3795 2 года назад

Your logic are too good, the way you break problem into such smaller/easier part is amazing.

@debasishphukon5345 2 года назад

Great Explanataion as always, I also wrote a recursive code for this, you guys can check it out : void findPermutation(string &ans, int k, int n, int st) //st is starting index { if(k==0) { return; } int f = factorial(n-1); int i = k/f; swap(ans[st], ans[st+i]); sort(ans.begin()+st+1,ans.end()); //O(nlogn) findPermutation(ans, k%f ,n-1,st+1); } I did swap instead of removing it from the array, this could be improved further by using erase function that striver used.

@Tomharry910 Год назад

Wonderful explaination. You walked us through the whole process with so much ease and clarity. Thank you for the good work!

@surajmisal3898 2 года назад

I just have completed this series. It's awesome and I'm looking forward to complete graph series now.

@Abhishek-do8mp 2 года назад

graph series is awesome too..

@namankeshari7332 Год назад

Extremely nicely explained! From brute force to most optimised approach with this detailed explanation, absolutely loved it!!!

@lokeshnegi5051 Год назад

finished the entire series thanks striver for this wonderful session on recursion.

@pallavivarshney1744 Год назад

Thanks it was really helpful. I have been following your sheet and it is really good. Please add more DP problems covering all categories of dynamic programming.

@codingloop Год назад

Completed entire playlist took 4-5 days and now I have good hold on Recursion & Backtracking . Thanks for your wonderful explanation and efforts

@lakshsinghania 11 месяцев назад

same

@escape704 Год назад

For the same que in interviewbit take care of the overflow condition when calculating the faction above numver 11... here is the code--- long factorial(long n){ if(n==0 or n==1) return 1; if(n>12) return INT_MAX; else return n*factorial(n-1); } string Solution::getPermutation(int n, int k) { vector nums; for(int i=1;i

@LegitGamer2345 3 года назад

i think this is the best explanation for this problem available on the internet EDIT : i think this is the best explanation for this problem available out there

@takeUforward 3 года назад

Glad it helped!

@akhileshsaga217 2 года назад

Thanks Striver, for amazing playlist on recursion.

@PraddyumnShukla Год назад

I think there's a mistake. In the second iteration when k = 4 and array = {1 , 2 , 4} then the 4th sequence will lie in the second block(the middle one) and not the in the last block. Because, the 3rd and 4th permutation is in the middle block whereas the 5th and 6th permutation is in the last block.

@swetajha2265 Год назад

We have to find the 17th element. 12 elements are already covered in the first iteration. Now we have to find the 5th element that would lie in the last block. Since it is 0 based, this confusion is there.

@luckydewangan5985 Год назад

Acutally he is considering 0 based indexing that's why you are consfused, by k=4 means 4th index ie 5th sequence

@user-vl7rw3ms2j 6 месяцев назад

Bhai hamne jab k=17 ko 16 bnaya, tabhi hamara k 0-indexing ka hissa ho chuka tha, meaning now our k is 0-indexed already. Hence k=4 lies in the third permutation set {1,2}

@mandeepkaur749 Год назад

these series are really great. A lot helpful and are a savior

@bhaveshkumar6842 2 года назад

@2:47 does making a deep copy involve converting an array of integers to an integer? Because to generate the permutations for 123, we'll use {1, 2, 3} and swap the array elements, so is deep copying converting an array of integers to an integer?

@aakriti1 2 года назад

Recursion series done🥳 Thanks a lot Striver Bhayiya! 😊

@kanikachauhan7391 Год назад

How come with these excellent teaching skills? Awesome playlist for recursion 🔥

@anirudhatalmale5575 3 года назад

Only one giving solution to problems which are very important and not being attempted by anyone else on youtube

@kira-nr3qj Год назад

we can do this question using binary exponentiation to get a more optimal solution, code - vector applyPermutation(vector sequence, vector permutation) { vector newSequence(sequence.size()); for(int i = 0; i < sequence.size(); i++) { newSequence[i] = sequence[permutation[i]]; } return newSequence; } vector permute(vector sequence, vector permutation, long long b) { while (b > 0) { if (b & 1) { sequence = applyPermutation(sequence, permutation); } permutation = applyPermutation(permutation, permutation); b >>= 1; } return sequence; }

@yuvraj2038 3 года назад

THANKYOUU SO SO MUCH FOR THIS SDE PLAYLIST :)

@indiansoftwareengineer4899 3 года назад

Thanks bhai, hope you are well now... great knowledge for free...

@vasujain1970 3 года назад

This is just gold

@dsa_tutorial Год назад

Thank You striver for this video actually i am generating all numbers and it is giving me TLE .Now I will Optimise the solution using this method .

@sanskarmaliwad4240 3 года назад

Loved the frequency of videos.Thank you bhaiya

@praveenrawat6574 11 месяцев назад

a very similar ques to this came in atlassian oa at my college, was able to solve this coz of u

@CodeSuccessChronicle 2 года назад

Clean, Clear, Well Structured Explanation Just Fantastic

@divyareddy7622 2 года назад

why is it 16%6 at 9:23

@CodeSuccessChronicle 2 года назад

@@divyareddy7622 it's been 4 months, I am unable to remember the pattern. I have to re-watch it again. But I did understand it so well, I'll definitely let you know after I watch it again and meanwhile I request you please watch again, this time you might get it. Try...

@divyareddy7622 2 года назад

@@CodeSuccessChronicle yess i did! He didn't explain properly the logic for 16mod6 ... I understood 16/6 but not 16mod6. Let me know when you're free!

@madarauchiha-dr5ws 2 года назад

@@divyareddy7622 here he did mod...reason is ... He initially divided the sequence in 4 groups. Now when he did / we know in which group our value resides. Now by doing % we now know at which place of that particular group this value resides. Hoping it is clear..let me know if not

@anishali8042 Год назад

@@divyareddy7622 8:52 Why 16%6? It is because there are 4 groups defined and in one of the 4 groups, the kth permutation will lie. 1, (2,3,4) Group 1

@dhanuufcdk 2 года назад

Awesome series. Really recommend it

@arpanbanejee5143 3 года назад

need one advice. Is it bad to use debugger of an ide to find out errors in my code for these kind of ques?

@madmax2442 3 года назад

Can we do something more efficient than erasing from a vector? as erase operation takes O(n) time.. and if n would have been larger, then we could have got TLE in this method. I thought of using a set.. but then we can't random access elements in a set like we do in vector. 'Ordered set' from Policy Based DS could do the work.. but is there any simpler way???

@sriharika2775 11 месяцев назад

Thank you so much for teaching in a simpler and understandable way..

@shubhiagarwal4047 3 года назад

yes this sheet is really underated please striver bhaiya complete your sde sheet as soon as possible i have seen almost all ..

@nehasingh9795 Год назад

Thankyou so much for making the best recursion playlist

@arpitomar7875 Год назад

Great explanation learned a lot from this series.

@tanuagrawal9921 2 года назад

Your explanation is best !!

@parthsalat 2 года назад

This one's complicated for me. I'm gonna keep this in my todo list.

@stith_pragya День назад

Understood,,,Thank you so much for this wonderful video....🙏🏻🙏🏻🙏🏻

@sauceopet 2 года назад

this content is gold. but this man ........... diamond !

@user-rs5is4zk4k 5 месяцев назад

God bless this guy!!

@priyajitpaul4190 Год назад

This was a tough problem but thanks to Striver bhaiya,gave a beautiful explanation which made it understand easily.😀

@salmankhader1258 Год назад

The another approach could be you can think of next permutation problem which gives the next permutation in o(n) time so you can call that function simply k times. it will be done in o(n*k) time

@sagardutta799 Год назад

2 reasons why using STL library is not promoted in this ques: 1. Whenever we write an algorithm for a code, it has to be universally applicable to all languages. Not all languages have in built next_permutation function 2. in worse case, the time Complexity will become O(n!) where n when 9 will make the program run for millions of times

@RaubinshArya 2 года назад

Completed this entire series and after watching this video I am going to request Leetcode to please mark this question as Easy not Hard. 😀

@nimitjain660 3 года назад

wonderful solution ans so easy!

@SubashsVlogs 3 года назад

Your content is the best one can get on RU-vid 🙌

@himadrinath1502 3 года назад

Bhiya mai expert hu codeforces mai kuch guide dijia how to reach candidate master my maximum rating in cf is 1700+ and I also 6* rating in codechef via short contest and 3 to 4 long contest is there very high leve genius Iq needed to reach very good rating in codeforces like that 2600+ in codeforces or any extra smart work needed to achive this beacuse some people are very short time to reach 2400+ rating in codeforces

@Aks-47 3 года назад

@@himadrinath1502 its evident from your what your saying...expert and 6 star ,my foot lol

@messyronaldo3161 3 года назад

@@himadrinath1502Kuchh jyada hi kamjor nhi h tu🤕🤕

@himadrinath1502 3 года назад

Tumara baat samja nahi bhai keya bola????

@himadrinath1502 3 года назад

Keya bola bhai??

@willturner3440 3 года назад

You're doing great brother 🤗

@harsimransingh8901 Год назад

Your work is really providing, Appereciable🙌

@vatalaaiswarya7956 2 года назад

You are really taking us forward. Please do moe videos. Your explantion is the best. None of the other's videos helps me like yours did 😊

@divyareddy7622 2 года назад

why is it 16%6 at 9:23

@-RohitJaiswal 2 года назад

@@divyareddy7622 Because we need to find the 16th permutation and 16 can be written as floor(16/k)*k + 16%k, we have jumped the first part i.e. floor(16/k)*k no. of permutations by deciding the first place, now we are just left with jumping the 2nd part i.e 16%k permutations.

@anishali8042 Год назад

@@divyareddy7622 8:52 Why 16%6? It is because there are 4 groups defined and in one of the 4 groups, the kth permutation will lie. 1, (2,3,4) Group 1

@prashanthreddy5006 3 года назад

Great Work bro Helping me a lot

@nitishkumargupta2787 2 года назад

Bruh..how do you explain so flawlessly

@AdityaDey424 2 года назад

How do I sort ? ArrayList al = .....

@vsrproduction1875 3 года назад

Thank you very much , it was helpful.

@ghoshdipan 3 года назад

Most awaited video on recursion!❤️

@dhrroovv Год назад

completed the playlist ... thanks

@envantoeditz6182 3 месяца назад

man , how he catch the pattern is literally amazing

@arpanbanejee5143 3 года назад

Excellent explanation! Don t know why there are so few likes!

@shwetanksingh5208 2 года назад

Isn't the brute force method for this question is to find (k-1) times next_permutation?

@irrompible4588 2 года назад

Amazing Explanation. I got placed because of learning how to explain recursion ..Your content has the biggest contribution..

@gauravshukla6675 2 года назад

which company??

@irrompible4588 2 года назад

@@gauravshukla6675 it's PeopleStrong

@tasneemayham974 Год назад

Hey, Striver!! I have a problem. Whenever I see your logic I can write the code easily. But the problem is it takes me a lot of time to figure out the logic and sometimes I don't know it. What do you think I should do to improve? May anyone help please. AND THANK YOU A MILLION FOR THE AMAZING SOLUTIONS AND A GREATER SERIESSS!!!!!!!!!!!!! 🔥🔥🔥👏👏

@Aman_Gupta54 2 года назад

damnnnn that was a very good explanation dude. keep it up

@TechInfochannel Год назад

Next permutation logic can also be used over here, but I has high complexity class Solution { public String getPermutation(int n, int k) { int arr[] = new int[n]; for(int i=0;i1){ nextPermutation(arr); } String s = ""; for(int i=0;i=1;i--){ if(arr[i]>arr[i-1]){ idx = i-1; break; } } if(idx==-1){ reverse(arr,idx+1,n-1); return; } for(int i=n-1;i>idx;i--){ if(arr[i]>arr[idx]){ swap(arr,i,idx);break; } } reverse(arr,idx+1,n-1); } private void reverse(int[] arr, int i, int j){ while(i

@abhisheksa6635 8 месяцев назад

Need to check way more times for this logic to set in.

@atharvakulkarni9033 2 года назад

first leetcode hard problem that I was able to solve by myself

@jacksparrow1316 3 года назад

Thank you bro.... awesome content

@cricketwala937 Год назад

I love the way you explains problem 😍

@bidishadas832 6 дней назад

This is the best explanation of this problem.

@AdityaSingh-uv3pe 2 года назад

Bruh Is it even possible come up with the optimal solution in under 1 hour or may be i'm just too dumb :'(

@rajeevnathani1153 2 года назад

Can we solve it using recursion like function calling the same function, without using the while loop ?

@AyushSachan2211 2 года назад

Yes

@rohankumarshah5679 2 года назад

int fact(int n) { if (n>12) return INT_MAX; int f = 1; for (auto i = 2; i fact(n)) return ""; int f = fact(n-1); int pos = k / f; k %= f; string ch = to_string(numlist[pos]); numlist.erase(numlist.begin() + pos); return ch + backtracking(k, numlist); } string Solution::getPermutation(int n, int k) { vector numlist; for (auto i = 1; i

@maneeshguptanalluru7807 2 года назад

Another approach to this problem: 1. Sort the array 2. Use the next permutation code as the subroutine 3. Repeat it k times to get the kth permutation TC - O(k*n)

@rishavsaha5254 2 года назад

@@prashantthakur9329 no the time complexity for next_permutation is O(n). His answer is also correct, but it's naive as in interview we are not expected to use such kind of STL. Like, if in interview you are asked to find the count of set bits for a number. You definitely won't say about the __builtin_popcount() STL.

@harshithravinoothala8157 2 года назад

The value of k is 10^9 so it will be taking a lot of time.

@amritanarang7305 3 года назад

2 videos in one day👍 osm bhaiya

@abhinavsrivastava2128 Год назад

Awesome explanation 👏. However the Java solution might not result in O(N) space if we dont keep ans as a StringBuilder. Not all languages are as bestowed as C++ where adding char to string is O(1)😅😅

@ankitbhardwaj9566 3 года назад

one thing i just didn't get was how time complexity was O(n2)

@brokegod5871 29 дней назад

O(n) to fix the positions one by one (n length permutation) throughout the while loop. O(n) for vector erase function at worst case to reach the nth position (begin starts from 0 and goes till n) if n is large

@DevangSharma 3 года назад

What is the intuition behind taking 0 based indexing of permutation

@takeUforward 3 года назад

Simple maths bro.. nothing like intuition

@subhajitdey135 7 месяцев назад

I think for the 3rd step, i.e. for {1,2}, k should be evaluated by 0%1 and not 0%0. Because the number of possible candidates is 1 each for {1,2}

@satendra6200 6 месяцев назад

yes Correct it should be 0 % 1 since size of each is 1 not 0

@harshgarg7025 3 года назад

Hey, we can optimize the time complexity to O(nlogn) by using other data structures instead of vectors or arrays.

@vaishnavisood9699 2 года назад

how?

@rakshitpandey7517 2 года назад

to store in sorted arrangement, it will be requiring NlogN to maintain the sorted order anyhow. You can't reduce that..

@shubhamdeshmukh9287 3 года назад

very good, awesome one

@spyrowolf2211 2 года назад

to come up with the optimal solution in a 30 minute interview is not "very simple" Striver, but regardless thank you for the walk-through of the best approach

@divyareddy7622 2 года назад

why is it 16%6 at 9:23

@anishali8042 Год назад

@@divyareddy7622 I hope you got the answer to why 16 % 6. Now please explain me that question's answer :(

@vamsikrishnasai1682 Год назад

Can we take all permutations using recursion and sort the result array and find the k th permutation?

@tushargogiya4017 Год назад

we can but its complexity is too High

@waltstone5445 Год назад

can someone explain why we use modula to find next val of k ? I cant understand the intuition

@nikhilrajsoni4541 Год назад

more formal way (taught by striver in his graph seiries): class Solution{ public: vectorx={1,0,0,-1}; vectory={0,-1,1,0}; string d="DLRU"; void solve(int i, int j,vector&a,int n,vector&ans,string move,vector&vis){ if(i==n-1&&j==n-1){ans.push_back(move);return;} for(int k=0;k

@sushant8686 2 года назад

i have done brute froce then why its showing tle because n can be only 9 I have changed no into string and then stored all permutations in a vector and then returned nth permutation