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-yd9tj2 жыл бұрын
this code is not working for a test case on interview bit kzbin.info/door/z9dtkYt27fb2priOSu_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 Жыл бұрын
It was unimaginable that i could ever learn DSA, but then i found you. Thanks a lot.
@aakstatic3 жыл бұрын
This series is so underrated! It deserves a lot more views. Thanks to Striver for doing this noble work. :)
@divyareddy76222 жыл бұрын
why is it 16%6 at 9:23
@harshkedia64932 жыл бұрын
@@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) .
@Zunan2632 жыл бұрын
Actually 💯
@nopecharon2 жыл бұрын
It's not underrated
@lakshsinghania Жыл бұрын
watched it 2 times to get the concept
@ghj72752 жыл бұрын
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❤❤❤
@harshtewari43332 жыл бұрын
Same
@YashHalgaonkar3 жыл бұрын
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; }
@freecoder5222 жыл бұрын
can I get the complete code
@YashHalgaonkar2 жыл бұрын
@@freecoder522 its complete.
@freecoder5222 жыл бұрын
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
@samratpodder5452 жыл бұрын
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 !!
@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
@adityamaheshwari30462 жыл бұрын
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)
@atjhamit2 жыл бұрын
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).
@lakshyaagarwal53018 ай бұрын
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 🥲
@atharvakalele372 жыл бұрын
This was a tough problem to grasp but u made us do anyway...u r awesome dude!
@lakshsinghania Жыл бұрын
indeed it was
@surajmisal38982 жыл бұрын
I just have completed this series. It's awesome and I'm looking forward to complete graph series now.
@Abhishek-do8mp2 жыл бұрын
graph series is awesome too..
@saranshpathak37952 жыл бұрын
Your logic are too good, the way you break problem into such smaller/easier part is amazing.
@escape7042 жыл бұрын
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
@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; }
@debasishphukon53452 жыл бұрын
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.
@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 Жыл бұрын
same
@PraddyumnShukla2 жыл бұрын
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
@PradyumanSharma-s4c9 ай бұрын
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}
@aakriti12 жыл бұрын
Recursion series done🥳 Thanks a lot Striver Bhayiya! 😊
@CodeSuccessChronicle3 жыл бұрын
Clean, Clear, Well Structured Explanation Just Fantastic
@divyareddy76222 жыл бұрын
why is it 16%6 at 9:23
@CodeSuccessChronicle2 жыл бұрын
@@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...
@divyareddy76222 жыл бұрын
@@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-dr5ws2 жыл бұрын
@@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
@LegitGamer23453 жыл бұрын
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
@takeUforward3 жыл бұрын
Glad it helped!
@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 .
@subhajitdey13510 ай бұрын
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}
@satendra62008 ай бұрын
yes Correct it should be 0 % 1 since size of each is 1 not 0
@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
@SubashsVlogs3 жыл бұрын
Your content is the best one can get on KZbin 🙌
@himadrinath15023 жыл бұрын
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-473 жыл бұрын
@@himadrinath1502 its evident from your what your saying...expert and 6 star ,my foot lol
@messyronaldo31613 жыл бұрын
@@himadrinath1502Kuchh jyada hi kamjor nhi h tu🤕🤕
@himadrinath15023 жыл бұрын
Tumara baat samja nahi bhai keya bola????
@himadrinath15023 жыл бұрын
Keya bola bhai??
@Tomharry910 Жыл бұрын
Wonderful explaination. You walked us through the whole process with so much ease and clarity. Thank you for the good work!
@parthsalat2 жыл бұрын
This one's complicated for me. I'm gonna keep this in my todo list.
@namankeshari7332 Жыл бұрын
Extremely nicely explained! From brute force to most optimised approach with this detailed explanation, absolutely loved it!!!
@praveenrawat6574 Жыл бұрын
a very similar ques to this came in atlassian oa at my college, was able to solve this coz of u
@sanskarmaliwad42403 жыл бұрын
Loved the frequency of videos.Thank you bhaiya
@sauceopet2 жыл бұрын
this content is gold. but this man ........... diamond !
@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
@pallavivarshney17442 жыл бұрын
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.
@mandeepkaur749 Жыл бұрын
these series are really great. A lot helpful and are a savior
@maneeshguptanalluru78072 жыл бұрын
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)
@rishavsaha52542 жыл бұрын
@@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.
@harshithravinoothala81572 жыл бұрын
The value of k is 10^9 so it will be taking a lot of time.
@stith_pragya2 ай бұрын
Understood,,,Thank you so much for this wonderful video....🙏🏻🙏🏻🙏🏻
@irrompible45882 жыл бұрын
Amazing Explanation. I got placed because of learning how to explain recursion ..Your content has the biggest contribution..
@gauravshukla66752 жыл бұрын
which company??
@irrompible45882 жыл бұрын
@@gauravshukla6675 it's PeopleStrong
@RaubinshArya2 жыл бұрын
Completed this entire series and after watching this video I am going to request Leetcode to please mark this question as Easy not Hard. 😀
@harshgarg70253 жыл бұрын
Hey, we can optimize the time complexity to O(nlogn) by using other data structures instead of vectors or arrays.
@vaishnavisood96993 жыл бұрын
how?
@rakshitpandey75172 жыл бұрын
to store in sorted arrangement, it will be requiring NlogN to maintain the sorted order anyhow. You can't reduce that..
@sriharika2775 Жыл бұрын
Thank you so much for teaching in a simpler and understandable way..
@anirudhatalmale55753 жыл бұрын
Only one giving solution to problems which are very important and not being attempted by anyone else on youtube
@envantoeditz61825 ай бұрын
man , how he catch the pattern is literally amazing
@bhaveshkumar68422 жыл бұрын
@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?
@abhisheksa663511 ай бұрын
Need to check way more times for this logic to set in.
@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)😅😅
@AshutoshAnand-o5l8 ай бұрын
God bless this guy!!
@lokeshnegi50512 жыл бұрын
finished the entire series thanks striver for this wonderful session on recursion.
@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!!!!!!!!!!!!! 🔥🔥🔥👏👏
@priyajitpaul4190 Жыл бұрын
This was a tough problem but thanks to Striver bhaiya,gave a beautiful explanation which made it understand easily.😀
@priyanshusain22747 күн бұрын
These type of questions require more memorization . So , we have to memorize the pattern of such type of questions?
@akhileshsaga2172 жыл бұрын
Thanks Striver, for amazing playlist on recursion.
@vatalaaiswarya79562 жыл бұрын
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 😊
@divyareddy76222 жыл бұрын
why is it 16%6 at 9:23
@-RohitJaiswal2 жыл бұрын
@@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
@kanikachauhan73912 жыл бұрын
How come with these excellent teaching skills? Awesome playlist for recursion 🔥
@gauravsharma-ho5hx2 жыл бұрын
recursive soln:- int fect(int n){ int product=1; for(int i=1;i
@rajeevnathani11532 жыл бұрын
Can we solve it using recursion like function calling the same function, without using the while loop ?
@AyushSachan22112 жыл бұрын
Yes
@rohankumarshah56792 жыл бұрын
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
@boostedsilverplays3 жыл бұрын
Man I feel like a genius after understanding the math behind the solution damn! Thanks raj 🙌🏻
@amritanarang73053 жыл бұрын
2 videos in one day👍 osm bhaiya
@ankitbhardwaj95663 жыл бұрын
one thing i just didn't get was how time complexity was O(n2)
@brokegod58713 ай бұрын
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
@utkarsh_1082 жыл бұрын
this ques somewhere pertains to Class 10th NCERT Maths book questions given in Examples section(maybe example 22 or 23 afaik) of chapter PNC the ques was like this, "If the letters of the word 'NAAGI' are arranged as in a dictionary then the rank of the given word...."
@dhruvchoubey47132 жыл бұрын
Do we have P&C in 10th? 😂
@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
@googleit2490 Жыл бұрын
Understood :) Was pretty tricky though... June'30,2023 10:43pm
@bidishadas8322 ай бұрын
This is the best explanation of this problem.
@arpitomar78752 жыл бұрын
Great explanation learned a lot from this series.
@vasujain19703 жыл бұрын
This is just gold
@nitishkumargupta27872 жыл бұрын
Bruh..how do you explain so flawlessly
@spyrowolf22112 жыл бұрын
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
@divyareddy76222 жыл бұрын
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 :(
@ghoshdipan3 жыл бұрын
Most awaited video on recursion!❤️
@AdityaDey4242 жыл бұрын
How do I sort ? ArrayList al = .....
@nehasingh97952 жыл бұрын
Thankyou so much for making the best recursion playlist
@madmax24423 жыл бұрын
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???
@indiansoftwareengineer48993 жыл бұрын
Thanks bhai, hope you are well now... great knowledge for free...
@shubhiagarwal40473 жыл бұрын
yes this sheet is really underated please striver bhaiya complete your sde sheet as soon as possible i have seen almost all ..
@dhrroovv Жыл бұрын
completed the playlist ... thanks
@harsimransingh8901 Жыл бұрын
Your work is really providing, Appereciable🙌
@cricketwala937 Жыл бұрын
I love the way you explains problem 😍
@tanuagrawal99212 жыл бұрын
Your explanation is best !!
@shwetanksingh52082 жыл бұрын
Isn't the brute force method for this question is to find (k-1) times next_permutation?
@PrajjwalNair Жыл бұрын
Can we use the logic for NextPermutationSequence here?😬 What I'm thinking of is having the 1st permutation and then using the logic (k-1) times. Do correct me.
@037_sayedramishali73 жыл бұрын
Khud se try kara 2 hrs mai nhi hua , video dekh ke smaj aaya thanx bhai🙏🙏
@tanmaysinghal83702 жыл бұрын
nice solution man, i'm thinking y u put this in the recurssion series?
@rajmehta64983 жыл бұрын
Thank you so much,great explanation!!
@DevangSharmayt3 жыл бұрын
What is the intuition behind taking 0 based indexing of permutation
@takeUforward3 жыл бұрын
Simple maths bro.. nothing like intuition
@rishukumarsingh3926 Жыл бұрын
Why k/fact(n-1) always gives the required index of the next number?
@yuvraj20383 жыл бұрын
THANKYOUU SO SO MUCH FOR THIS SDE PLAYLIST :)
@subhaghanta24382 жыл бұрын
Bhaiya es question may, 2nd time k=4 lay kiye apne but k-1 = 3, K=3 hoga i think... Please clarify someone
@ushmitadutta67132 жыл бұрын
Completed the entire series
@nikhilmehta49513 жыл бұрын
Can we not solve this using 1 based indexing?
@shubhamkumar3198 Жыл бұрын
Awesome playlist
@dhanuufcdk2 жыл бұрын
Awesome series. Really recommend it
@devanshupadhyay2658 Жыл бұрын
the best playlist ever.
@LegitGamer23453 жыл бұрын
13:45 shouldnt it be 0%1 instead of 0%0
@LegitGamer23453 жыл бұрын
also , we can use hashmaps and doubly linked lists so that remove becomes O(1) , here we have distinct numbers so for every number we can use it as key in hashmap with value as node , so we can get the node at any moment , after getting the node we can achieve remove in O(1)
@prasunkirtania42212 жыл бұрын
Yes bro fact =1 at there .. so 0/1 = 0
@arpanbanejee51433 жыл бұрын
need one advice. Is it bad to use debugger of an ide to find out errors in my code for these kind of ques?
@immrhrr11 ай бұрын
class Solution { public: string getPermutation(int n, int k) { // Initialize fact to 1 (not 0) int fact = 1; vector numbers; // Initialize fact and push numbers from 1 to n for (int i = 1; i
@atharvakulkarni90332 жыл бұрын
first leetcode hard problem that I was able to solve by myself
@willturner34403 жыл бұрын
You're doing great brother 🤗
@ravishankardas48562 жыл бұрын
for better complexity run the while loop till n
@saranghae37202 жыл бұрын
C++ Code class Solution { public: string getPermutation(int n, int k) { int fact = 1; vector nums; for(int i = 1; i
@waltstone5445 Жыл бұрын
can someone explain why we use modula to find next val of k ? I cant understand the intuition
@AdityaSingh-uv3pe3 жыл бұрын
Bruh Is it even possible come up with the optimal solution in under 1 hour or may be i'm just too dumb :'(
@rachitagrawal35702 жыл бұрын
Thanks for helping.
@shrad66112 жыл бұрын
Java Version of Code: public class Solution { public String getPermutation(int n, int k) { List numbers = new ArrayList(); StringBuilder sb = new StringBuilder(); // create an array of factorial lookup int fact = 1; for(int i=1; i
@ritikshandilya70756 ай бұрын
Thanks for wonderful session Striver 🐯
@arpanbanejee51433 жыл бұрын
Excellent explanation! Don t know why there are so few likes!