Next Permutation | Leetcode #31
Vložit
- čas přidán 6. 09. 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
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!
So far the best content I have ever seen and best channel for DS and Algo.
Thanks :)
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.
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 😀
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.
Great explanation thank you
Welcome 😊
Can u pls explain the last line of code that starting from sort(nums.begin()......
I was struggling with this question. You made it easier ..thank you so much for this amazing explanation!!
wow! reduction at work guys. The whole world is running upon two things 1. reduction 2. approximation.
great explaination of the question
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 :)
That graph representation just blew my mind.
I no longer dread this problem, great explanation!
i am always looking for this channel if i want explaination of any questions . saves me a lot of time !!! 💛
Great ❤️
What if we get peak at 0th index but other half is not sorted..
eg. 3 1 2
beautiful explanation
was looking for this Question and then you just uploaded this video.
Best explanation for this Question !!!!
Thanks :)
If you get this qn in an interview... u can easily pass time by explaining this approach... btw crystal clear explanation sir🙏
Thanks 😊
rather than sorting we can reverse it, so making the complexity go from o(nlogn) to o(n)
Great Explanation, but I still think this is an Awful Question for an Interview.
Great Great .. Explained well with different cases... All of my queries are resolved .. thank you so much ..
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
Very well explained 🤜
Great explanation
Best explanation i have ever seen
very much better than striver
Bhai can you also provide the code in java in the upcoming videos. It would be very helpful for many of java geeks.
Very useful one. Thank you sir
OMG!!! I'm feeling lucky that CZcams recommend me your channel🥰, You are amazing!!....Thank you for the good work sir!
Welcome :)
Great explanation sir!, I find this problem difficult to solve, but after watching your video, it makes me easy to solve.
Thanks
i was able to come up with the 70% approach
amazing explanation with diagram approach
This is the best explaination about this problem, thank you so much 🙏
Thanks :)
such a great explanation
Best explanation for this problem....👍👍
Thank you so Much for such a detailed explanation...🙂
Welcome : )
you deserve more likes yar... great video
Amazing explanation😍
The best of all 🎉🔥please keep onposting
Thanks
beautifully explained!!!
thank you so much for such a beautiful explanation may god bless you
This was amazing description thank you
The explanation is so good and every detail is covered throughly. A hard problem made easy. Thank You so much:)
Welcome :)
Thanks, i like ur videos the most among all.
thank you so sooo much.. the explanation is great ..
Welcome
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
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
Graph helped thank you
Great ❤️
can anyone tell me what kind of questions is this i mean under which concept is it coming ?
Brilliant !
Thank you, Sir, this was nice
Great explanation. Thanks a lot
Bhai you are the best
Thanks :)
Thank you!
Welcome
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
This channel saves me everytime:)
❤️
Maja aagya sir 🙌
Thanks 😊
why we dont just use next_permutation ?
Thanks a lot!
Best explanation 🧡
Welcome
What is the time complexity here?
nlogn
Really appreciated ❤️
Thanks :)
Freakinnnn Awesommmeee
Thanks .it helped me understood
Wow! such a clear explanation...thank you
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
Thank you man, you helped me! Very clear
It's not working.
Well explained 👌🏻👌🏻💯💯
Thanks
Good Explanation! Thank You
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 👍👍
Code link doesn't work, getting 404.
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.
Better than striver
Level ka observation h vaiya
genius...:)
Awesome Teacher
Thanks
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].
At 4:30 your explanation is not correct... If you check the striever video explanation then you can spot the mistake
Sir plz apni facevalue bhi banaaiye
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!
Amazing ;)
:)
Appreciate
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
medium btw
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 )
amazing explanation
Thanks :)
Thanks!
Welcome 😀
Great explanation
Great explanation