For all those who are getting confused about the usage of the min variable in the code. It is actually not needed at all. The thing is, in the second part of algo, when we are moving from infpt to the end of the array and comparing every element with toswap value, it is by default that everything after inftp position is already in descending order, so the algorithm in step 2 will automatically swap with the next larger element from toswap value. Take this test case [2,7,5,3,1] and visualize it by writing down each step.
Better version of code with no confusion :- void nextPermutation(vector& nums) {
// Let,s try to find out the inflation point and alwz find from the back // which is firstpoint from back which breaks the rule // to swap point is just left index of inf point
int n = nums.size(); int infpt = -1; int toswap = -1;
for(int i = n-1 ; i>=0 ; i--) {
if( i>0 && nums[i-1] < nums[i]) {
infpt = i; toswap = i-1;
break;
}
}
if(infpt == -1) //that means order is correct just need to reverse to get next permutation reverse(nums.begin(),nums.end()); else {
// if we found the inflation point now we need to find the candidate no which we have to swap
//lets go from back till inf point and find out the first no which is greater
for(int i = n-1 ; i>= infpt ; i--) {
if(nums[i] > nums[toswap]) {
swap(nums[i],nums[toswap]); break;
}
}
// step 3 => reverse the nos from the inflation point to the last for get the next permutation
This helps me much. Please do a series on Dynamic Programming, It would be helpful for some xperienced professional like me who wanted to crack Product companies
Why did you not use swap function to swap nums[j] and nums[infpt-1]....... i was using the swap function , the progam was showing error, but when I manually did it..... it got accepted .. can you please explain?
Line 37: Char 18: error: no member named 'nextPermutation' in 'Solution'; did you mean 'nextPermuatation'? Solution().nextPermutation(param_1); ^~~~~~~~~~~~~~~ nextPermuatation Line 4: Char 8: note: 'nextPermuatation' declared here void nextPermuatation(vector & nums){ ^ 1 error generated. WHAT WAS THAT
For all those who are getting confused about the usage of the min variable in the code. It is actually not needed at all.
The thing is, in the second part of algo, when we are moving from infpt to the end of the array and comparing every element with toswap value, it is by default that everything after inftp position is already in descending order, so the algorithm in step 2 will automatically swap with the next larger element from toswap value. Take this test case [2,7,5,3,1] and visualize it by writing down each step.
gotcha
Better version of code with no confusion :-
void nextPermutation(vector& nums) {
// Let,s try to find out the inflation point and alwz find from the back
// which is firstpoint from back which breaks the rule
// to swap point is just left index of inf point
int n = nums.size();
int infpt = -1;
int toswap = -1;
for(int i = n-1 ; i>=0 ; i--)
{
if( i>0 && nums[i-1] < nums[i])
{
infpt = i;
toswap = i-1;
break;
}
}
if(infpt == -1) //that means order is correct just need to reverse to get next permutation
reverse(nums.begin(),nums.end());
else
{
// if we found the inflation point now we need to find the candidate no which we have to swap
//lets go from back till inf point and find out the first no which is greater
for(int i = n-1 ; i>= infpt ; i--)
{
if(nums[i] > nums[toswap])
{
swap(nums[i],nums[toswap]);
break;
}
}
// step 3 => reverse the nos from the inflation point to the last for get the next permutation
reverse(nums.begin()+infpt,nums.end());
}
}
};
Thanks
This is the second time I have watched one of your videos and received a clear conise explanation of what needs to be done - thanks again.
class Solution {
public:
void nextPermutation(vector& nums) {
next_permutation(nums.begin(),nums.end());
}
};
🤣
Leave the answer that anyone can find it..The most important thing is you made me understand the question quickly. Thank you
This helps me much. Please do a series on Dynamic Programming, It would be helpful for some xperienced professional like me who wanted to crack Product companies
def solve(nums):
find idx1
find idx2
swap(nums[idx1],nums[idx2])
reverse(nums[idx1+ 1 till end)
why arent we updating min inside the if statement?
same doubt
have you got the solution?
I hope i could add an audio message. . .The simple and execution is wow...looked across entire youtube. but this one is 😌
please tell me you are not updating the min then how u r getting the correct ans....??
exactly how does min work? even if you remove the min statement its working
exactly
@@arshdeep011 exactly without that also u will get the same result.
due to limited test cases on leetcode ,we need to modify the code a little bit for sure to update min
awesome explanation
Perfect explanation of code 👌
Nicely explained 🙂🙂
how is this algo working for three digits numbers ? can u please explain?
NICE SUPER EXCELLENT MOTIVATED
Why did you not use swap function to swap nums[j] and nums[infpt-1]....... i was using the swap function , the progam was showing error, but when I manually did it..... it got accepted .. can you please explain?
may be these function are applicable on vectors only...not on the array.
What if nums contains 0 as element?
You are the best mam. Thank you so much😊😊
why did you run the first loop backwards?
how we can say this algorithm take O(N) time. we all now that sort function take O(NlogN). ???
address sanitizer error is coming in leetcode. why?
Line 37: Char 18: error: no member named 'nextPermutation' in 'Solution'; did you mean 'nextPermuatation'?
Solution().nextPermutation(param_1);
^~~~~~~~~~~~~~~
nextPermuatation
Line 4: Char 8: note: 'nextPermuatation' declared here
void nextPermuatation(vector & nums){
^
1 error generated.
WHAT WAS THAT
Spelling galat hai teri
can anyone tell me we swapped with 3 or 5 in the above code.
for the first time iteration we swapped nums[j], with nums[infn-1]
Tq so much eagerly we r waiting yr next video
U explain very well
please explain me why line no. 26?
Fantastic explanation 👍
It was worth subscribing your channel😀😁
Thanks a lot Di....👏
I can't understand this problem can anyone explain?
+1
No need of min
Jus to this-
for(int j=inftp ; j
i think this reply is helpful who has doubt in line 26
what is the time complexity for solving this?
It'll be O(n) i guess..
💯💯
nice explanation
just wow