Next Permutation | Leetcode #31
ฝัง
- เผยแพร่เมื่อ 22 ส.ค. 2024
- This video explains the next permutation problem which uses a very unique concept of creating the next greater sequence from an array. I have shown the entire intuition step by step using simple examples with reasons for each step.Please watch the entire video to get all the required concepts.
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 :)
======================================PLEASE DONATE=============================
🧡 SUPPORT OUR WORK: / techdose
💚 UPI-ID: surya.kahar@ybl
💞JOIN Membership: / @techdose4u
==============================================================================
INSTAGRAM : / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
USEFUL LINKS:
🟠Must do TIPS to ACE Virtual Interview: • 🔴Must do Tips to ACE y...
🟢Best strategy to excel your coding interview: • 🔴Best strategy to exce...
🟡Get your dream job in 1 month: • 🔴Get your dream job in...
🔵How to crack dream job in just 2 months: • How to crack dream job...
🟣7 Days DSA plan: techdose.co.in...
RELATED LINKS:
Permutation Sequence: • Permutation Sequence |...
String permutation algorithm: • String permutation alg...
Permutation in a string: • Permutation in String ...
CODE LINK: techdose.co.in...
Great explanation! I think this approach can be modified to make the complexity O(n) by avoiding sorting. After swapping is done, it can be observed that all elements after the left index selected for swapping till the end of the array will be reverse sorted. So, we only need to reverse array after the left swapped index.
Great :)
Yes this is true
pin this comment. :)
Pin this comment plz
For this to work, nums[i]
Great explanation, how the hell do we come up with a solution with so many edge cases in an interview where you have 30 minutes at best? 😩
after 2 years how it feels
So far the best content I have ever seen and best channel for DS and Algo.
Thanks :)
At first I was confused by what the question was actually asking, but watching the whole explanation it became clearer and the approach really made sense. Thanks!
:)
This is absolutely the best explanation I found after almost getting paralyzed by the question. Thanks!
More simpler approach:
public void nextPermutation(int[] nums) {
int n=nums.length;
if(n=0 && nums[i]>=nums[i+1])
i--;
if(i>=0){
int j=n-1;
while(nums[j]
O(n) code:
public void nextPermutation(int[] nums) {
int peak = nums.length-1;
// find peak from right
while(peak>0) {
if(nums[peak] > nums[peak-1]) {
break;
}
peak--;
}
if(peak==0) { // all numbers are descending, so reverse
reverse(nums, 0, nums.length-1);
} else {
int i = peak-1;
int j = nums.length-1;
// find a number greater than that at i and has as low weight as possible
// this is to find lowest number greater than the number to be swapped so that we can get next higher number
while(j>i && nums[i] >= nums[j]) j--;
swap(nums, i, j); // i+1 till end of array is descending ordered
if(i
Best explanation i have seen. I was unable to understand what is next permutations. U taught me that. Thank you 😊
Welcome 😀
wow! reduction at work guys. The whole world is running upon two things 1. reduction 2. approximation.
Here's the logic in simple terms without the confusion of multiple special cases. Since a descending sequence is already at its largest value, we can't get the next larger sequence from it. We therefore find the first ascending pair a[i] > a[i-1] from the end, and swap a[i-1] with the smallest possible value on the right that is larger than it. Since a[i-1] has been increased in value, the sequence a[i:] must be set to its smallest value to give the smallest next larger sequence, which is given by the ascending order. Furthermore, since we swapped a[i-1] with the smallest possible value on the right, say a[j], all elements in sequence a[j+1:] are smaller than a[i-1], and all elements in the sequence a[i:j] are larger than a[i-1]. Thus, the sequence a[i:] is in descending order, and can be made ascending by using two pointers to swap elements from both ends.
It is almost impossible to come up with a solution to this in an interview setting, if you haven't already solved this question before.
It is one of those questions, if you know, you know.
This is O(n) , we don't require the last sorting part as the elements are already sorted but in reverse order. So simply swapping that would works.
That graph representation just blew my mind.
i am always looking for this channel if i want explaination of any questions . saves me a lot of time !!! 💛
Great ❤️
I no longer dread this problem, great explanation!
I was struggling with this question. You made it easier ..thank you so much for this amazing explanation!!
If you get this qn in an interview... u can easily pass time by explaining this approach... btw crystal clear explanation sir🙏
Thanks 😊
Great Explanation, but I still think this is an Awful Question for an Interview.
Great explanation thank you
Welcome 😊
best explanation so far.. there was some part which should have explanied more with the code though..
Sir in all your previous vides I used to get the logic pretty easily....but in this video I struggled a lot....I think the question is quite tricky..
Yes it is :)
great explaination of the question
OMG!!! I'm feeling lucky that TH-cam recommend me your channel🥰, You are amazing!!....Thank you for the good work sir!
Welcome :)
was looking for this Question and then you just uploaded this video.
Best explanation for this Question !!!!
Thanks :)
you deserve more likes yar... great video
beautiful explanation
Can u pls explain the last line of code that starting from sort(nums.begin()......
Very well explained 🤜
Best explanation i have ever seen
The best of all 🎉🔥please keep onposting
Thanks
Great explanation
i was able to come up with the 70% approach
very much better than striver
What if we get peak at 0th index but other half is not sorted..
eg. 3 1 2
Great explanation sir!, I find this problem difficult to solve, but after watching your video, it makes me easy to solve.
Thanks
This is the best explaination about this problem, thank you so much 🙏
Thanks :)
The explanation is so good and every detail is covered throughly. A hard problem made easy. Thank You so much:)
Welcome :)
Great Great .. Explained well with different cases... All of my queries are resolved .. thank you so much ..
Amazing explanation😍
Very useful one. Thank you sir
Maja aagya sir 🙌
Thanks 😊
amazing explanation with diagram approach
Best explanation for this problem....👍👍
Thank you so Much for such a detailed explanation...🙂
Welcome : )
Too many edge cases in the explaination, but code doesn't have many. Ayushi Sharma has also provided with good explaination, incase you feel this video is li'l tough
beautifully explained!!!
such a great explanation
Thanks, i like ur videos the most among all.
This channel saves me everytime:)
❤️
Bhai can you also provide the code in java in the upcoming videos. It would be very helpful for many of java geeks.
This was amazing description thank you
Bhai you are the best
Thanks :)
Graph helped thank you
Great ❤️
Freakinnnn Awesommmeee
thank you so sooo much.. the explanation is great ..
Welcome
Cant we replace the last for loop by :
int index = lstpeak;
if (arr[lstpeak + 1] > arr[lstpeak - 1]) index = lstpeak + 1;
EDIT: no we cant , we need to replace lst-1 with the minimum element in the right of lstindex
amazing explanation
Thanks :)
rather than sorting we can reverse it, so making the complexity go from o(nlogn) to o(n)
Great explanation. Thanks a lot
Brilliant !
Thanks a lot!
Best explanation 🧡
Welcome
thank you so much for such a beautiful explanation may god bless you
Thank you!
Welcome
Really appreciated ❤️
Thanks :)
Thank you man, you helped me! Very clear
It's not working.
can anyone tell me what kind of questions is this i mean under which concept is it coming ?
Wow! such a clear explanation...thank you
Thanks!
Welcome 😀
Thanks .it helped me understood
Can you explain Integer to English words leetcode 273 problem ?
Sure. It's very important for FAANG :)
@@techdose4u Word break and word break 2 problems . Expecting these two from you long back very important for all FAANG . Can you please take these two into your list ? Thank you for helping us.
Sure
Well explained 👌🏻👌🏻💯💯
Thanks
Level ka observation h vaiya
What is the time complexity here?
nlogn
very appreciate your hard work, seen many videos regarding the same topic, Found your video the best explanation and clearing all blurry clouds. Thanks again😊😊. All the best 👍👍
at 16:12 u said that , if u have to swap the last n-1 elements the time complexity will be nlogn, but is there is a possibility that , last n-1 will be sorted in decreasing order , so we can use two pointers to make it sorted in increasing order,resulting in optimized time complexity of O(n/2) or O(n) ?
Thanks
Better than striver
Hi Suriya bro,
I've one doubt. Can you please clarify for me?
Last 3 years I'm working as a manual and automation tester in Embedded Networking, somehow I entered into this domain, but I've been self-interested in coding & want to be a developer. but, in the developer interview, I don't have an experience of dev to show. I'm not getting interested to work on testing, my minds want to be a developer but not able to do. It's internally hurting me a lot. what to do? Need your suggestion, please.
Replied
why we dont just use next_permutation ?
Good Explanation! Thank You
Awesome Teacher
Thanks
genius...:)
Code link doesn't work, getting 404.
medium btw
what a horrible question , the only way is to memorize this - it needs a trick to know. read the comments under the official solution on leetcode! they all complain and justfiedly
This was beautiful, thank you
excellent explanation. just one thing. instead of sorting the last part we can just reverse it in o(n/2) time since it will always be in descending order. but in this case we just have to make sure if there are two places where i can make a change then i select the further one.eg:[2,3,1,3,3].
Sir plz apni facevalue bhi banaaiye
Amazing ;)
:)
Plz make a detailed video on how to develop LinkedIn profile so strong that recruiters Of top companies can't resist to give job opening opportunities and internship opportunities specially for 2020grads (unplaced)
The only secret to nailing Linkedin is to be successful in real life. Do extraordinary things only when that will happen; No shortcuts whatsoever
@@iamparitosh along with good work, if you customize your account to make it look more presentable, it can help too!
Appreciate
Found a mistake 12:51 [2,4,3,2] -> ngs is not [2,4,2,3]
The peak element here is 4 . ig we have to swap 4 with 2.
At 4:30 your explanation is not correct... If you check the striever video explanation then you can spot the mistake
Worst explanation ever
how did you rearrange the next greater sequence, its confusing as I am not understanding whats the next greatern sequence means
Minimum of all greater permutations of given number. Ex 1386 -> Next minimum should be 1638 ( It is lowest of any combination of greater permutations )
Thank you, Sir, this was nice
Great explanation
Great explanation