Next Permutation - LeetCode 31 - Python [O(n) time and O(1) Space!]

Explaining how to solve Next Permutation in Python - LeetCode 31!

Music: Bensound
Hit me up if you have any questions!:)

[Ankit-hsnb]

Another great video!
we can use this logic maybe for swapping:

nums[ind1], nums[ind2] = nums[ind2], nums[ind1]

[JRMAMS]

ANOTHER AMAZING EXPLANATION BY THE LEETCODE QUEEN :)

[shubhamh]

With the first algorithm, i was like, damn, I built the exact same logic but it did not work on all cases. But then with the slightly different approach, it works. Thank you, keep up!

[jlozano]

For some reason, the first approach works on some cases but on others it doesn't. The second approach (5:11) worked great. Thanks!

[divyatalesra]

Really great!!! Thanks so much!!! Wow!!!

[mydalaharsha]

very well explained, thank you so much for the solutions. I want to know how did you start learning DSA. I'm switching to software engineering from different background, if there is any good book that you followed while preparing can you let me know please

[tejeshwararaothella]

you can assign a variable for lenght of array, which saves computational power

[nikhilmishra]

Straight to the point and easy to understand. Thanks!

[amanshaukat]

you earned a new code writing skill is very nice, it's clean and will try to imitate you

[swagatpatra]

impressive coding skills. The accent though helped me understand better.
the same thing in java
// [1, 7, 9, 9, 8, 3]
// index = 1
// sort from index 3 till end
// swap 7 with just larger to right
public void nextPermutation(int[] nums) {
int n = nums.length;
if(n<2) return;

int index = -1; int i = n-1;
while(i>0){
if(nums[i]>nums[i-1]) {
index = i-1;
break;
}
i--;
}

if(index == -1) reverseSort(nums, index+1, n-1);
else{
reverseSort (nums, index+1, n-1);
for(i = index+1; i<n; i++){
if(nums[i]>nums[index]) {
swap(nums, index, i);
break;
}
}
}
}

void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}

void reverseSort(int[] arr, int start, int end){
while(start <= end){
swap(arr, start++, end--);
}
}

[praweenkr]

just_great thanks you sharing. pls continue making more such videos

[samsonkolge]

For swapping you could do it in one line in python: i1, i2 = i2, i1

[lukt]

Great explanation, thank you! :) One thing I also found is that we don't necessarily need to check if next_num is less than len(nums) in line 28, since there must be a number larger than nums[dec], otherwise we would have a returned in line 26 earlier.

[devedroy]

a lil confusion on how you found the next greater number after reversing the right part of the array.

[prithviraj]

I saw other videos on this question but i wasnt able to understand.then
Watched your video and understood in first go...great work ..keep it up

[jeremyliang]

Awesome explanation! Finally understood this question! Thanks!

[anujkhare]

thanks a lot it helped me so much, but here's one suggestion though, i think you must have spent a little bit more time on cases where digits were repeating.
i appreciate you taking the example - { 1, 7, 9, 9, 8, 3} .I guess this example was really significant because this is one of the cases which people tend to forget ( that we might encounter digits repeating).
Another great example could be taking - {1, 7, 9, 9, 8, 7, 3} and these two examples would cover both the = sign in comparisons.
Anyways, great explanation.
thankyou

[linglin]

Very good explanation! Easy to understand! Thank you very much!

[PhoenixRisingFromAshes]

GREAt your second approach is on first approach has a problem in dealing with duplicates . If the next greater element of arr[index-1] is duplicated then we need to swap with the rightmost only because if we do not then after reversing, smaller element will move furthur to the least significant positions which is spot on

[nooshinyousefi]

You are so good in explaining, please upload more post and more questions