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.
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!
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
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.
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.
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
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) ?
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
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.
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
@@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.
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].
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)
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 👍👍
Minimum of all greater permutations of given number. Ex 1386 -> Next minimum should be 1638 ( It is lowest of any combination of greater permutations )
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
After 3 years ?
You don't. You simply memorize it.
That's why you spend hundreds of hours practicing DSA problems
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!
:)
That graph representation just blew my mind.
wow! reduction at work guys. The whole world is running upon two things 1. reduction 2. approximation.
This is absolutely the best explanation I found after almost getting paralyzed by the question. Thanks!
YES! THIS QUESTION IS VERY CONFUSING
So far the best content I have ever seen and best channel for DS and Algo.
Thanks :)
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.
I no longer dread this problem, great explanation!
very much better than striver
I was struggling with this question. You made it easier ..thank you so much for this amazing explanation!!
Best explanation i have seen. I was unable to understand what is next permutations. U taught me that. Thank you 😊
Welcome 😀
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
I really understood this after watching 3 videos, the graph and peak explanation with decimal breakdown made it clear
nice :)
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 😊
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]
Great Great .. Explained well with different cases... All of my queries are resolved .. thank you so much ..
i am always looking for this channel if i want explaination of any questions . saves me a lot of time !!! 💛
Great ❤️
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.
Best explanation i have ever seen
best explanation so far.. there was some part which should have explanied more with the code though..
You're the best 🎊💯. The explanation was enough for me to code it up.
nice :)
you deserve more likes yar... great video
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.
My goodness, this is an absolute banger of an explaination. tysm
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
This was amazing description thank you
OMG!!! I'm feeling lucky that UA-cam recommend me your channel🥰, You are amazing!!....Thank you for the good work sir!
Welcome :)
Great Explanation, but I still think this is an Awful Question for an Interview.
amazing explanation with diagram approach
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 :)
it was a great explanations video. i finally understand the #concept
Best explanation for this problem....👍👍
Thank you so Much for such a detailed explanation...🙂
Welcome : )
Can u pls explain the last line of code that starting from sort(nums.begin()......
Very useful one. Thank you sir
The best of all 🎉🔥please keep onposting
Thanks
can anyone tell me what kind of questions is this i mean under which concept is it coming ?
Thanks, i like ur videos the most among all.
What if we get peak at 0th index but other half is not sorted..
eg. 3 1 2
beautifully explained!!!
Very well explained 🤜
Amazing explanation😍
beautiful explanation
Great explanation thank you
Welcome 😊
such a great explanation
This channel saves me everytime:)
❤️
The explanation is so good and every detail is covered throughly. A hard problem made easy. Thank You so much:)
Welcome :)
Sorting is not required, we can just reverse that decreasing sequence in the end. It will automatically sort the array
Wow! such a clear explanation...thank you
thank you so sooo much.. the explanation is great ..
Welcome
thanks dude, this is a very helpful vedio
welcome :)
Thank you man, you helped me! Very clear
Thank you, Sir, this was nice
Great explanation
Great explanation. Thanks a lot
Good Explanation! Thank You
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
Thanks .it helped me understood
Thanks a lot!
Best explanation 🧡
Welcome
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
Really appreciated ❤️
Thanks :)
Graph helped thank you
Great ❤️
thank you so much for such a beautiful explanation may god bless you
Maja aagya sir 🙌
Thanks 😊
Brilliant !
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
Bhai can you also provide the code in java in the upcoming videos. It would be very helpful for many of java geeks.
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
genius...:)
Bhai you are the best
Thanks :)
What is the time complexity here?
nlogn
This was beautiful, thank you
Well explained 👌🏻👌🏻💯💯
Thanks
you're the man broo! Thx!
Thanks 🙏🏼
rather than sorting we can reverse it, so making the complexity go from o(nlogn) to o(n)
Awesome Teacher
Thanks
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
NICE SUPER EXCELLENT MOTIVATED
nice :)
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
why we dont just use next_permutation ?
It's not working.
Code link doesn't work, getting 404.
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].
Amazing 🤩
thanks :)
Level ka observation h vaiya
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!
At 4:30 your explanation is not correct... If you check the striever video explanation then you can spot the mistake
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 👍👍
Amazing ;)
:)
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
Sir plz apni facevalue bhi banaaiye
Appreciate
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 )