Next Permutation | Leetcode #31

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...

[@life_of_anjali]

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.

[@techdose4u]

Great :)

[@splinkerp2222]

Yes this is true

[@glenfernandes253]

pin this comment. :)

[@niteshkhetan9757]

Pin this comment plz

[@prakharsankrityayan1300]

For this to work, nums[i]

[@darshansimha2166]

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? 😩

[@BiplabSutradhar-c8e]

after 2 years how it feels

[@bthulasikrishna9597]

After 3 years ?

[@srikantd6054]

So far the best content I have ever seen and best channel for DS and Algo.

[@techdose4u]

Thanks :)

[@vcfirefox]

This is absolutely the best explanation I found after almost getting paralyzed by the question. Thanks!

[@Cocoblu2]

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!

[@techdose4u]

:)

[@art4eigen93]

wow! reduction at work guys. The whole world is running upon two things 1. reduction 2. approximation.

[@parthokr]

That graph representation just blew my mind.

[@gouthamr8214]

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.

[@chiragsahu5468]

Best explanation i have seen. I was unable to understand what is next permutations. U taught me that. Thank you 😊

[@techdose4u]

Welcome 😀

[@aditisinghh]

i am always looking for this channel if i want explaination of any questions . saves me a lot of time !!! 💛

[@techdose4u]

Great ❤️

[@payalshekhawat7563]

I was struggling with this question. You made it easier ..thank you so much for this amazing explanation!!

[@dikshantboora3764]

very much better than striver

[@abhishekjadoun7562]

was looking for this Question and then you just uploaded this video.
Best explanation for this Question !!!!

[@techdose4u]

Thanks :)

[@afridimajeed5897]

I no longer dread this problem, great explanation!

[@pratosh]

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]

[@paragroy5359]

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..

[@techdose4u]

Yes it is :)

[@minatokuns1810]

best explanation so far.. there was some part which should have explanied more with the code though..

[@abhijit-sarkar]

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.

[@alwinsanthosh6878]

My goodness, this is an absolute banger of an explaination. tysm

[@madhavanr8996]

Can u pls explain the last line of code that starting from sort(nums.begin()......

[@tanishhhhhhh]

great explaination of the question

[@krentwhite2668]

If you get this qn in an interview... u can easily pass time by explaining this approach... btw crystal clear explanation sir🙏

[@techdose4u]

Thanks 😊

[@praharshsingh2095]

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) ?

[@BMEARJUNSINGH]

Thanks

[@TheSridharraj]

Best explanation i have ever seen

[@dhanashreegodase4445]

you deserve more likes yar... great video

[@shobhanksharma65]

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

[@satheeshshanmugam5940]

Great Great .. Explained well with different cases... All of my queries are resolved .. thank you so much ..

[@mohdfarhanahmed9416]

Bhai can you also provide the code in java in the upcoming videos. It would be very helpful for many of java geeks.

[@manojs157]

Great explanation thank you

[@techdose4u]

Welcome 😊

[@sekharsamanta6266]

Wow! such a clear explanation...thank you

[@jlecampana]

Great Explanation, but I still think this is an Awful Question for an Interview.

[@Ajeet-Yadav-IIITD]

OMG!!! I'm feeling lucky that RUclips recommend me your channel🥰, You are amazing!!....Thank you for the good work sir!

[@techdose4u]

Welcome :)

[@selvaprasanths2202]

The best of all 🎉🔥please keep onposting

[@techdose4u]

Thanks

[@johncenakiwi]

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.

[@thinkverse94]

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.

[@techdose4u]

Replied

[@harpercfc_]

Very useful one. Thank you sir

[@stark3.148]

Sorting is not required, we can just reverse that decreasing sequence in the end. It will automatically sort the array

[@大盗江南]

Thanks, i like ur videos the most among all.

[@ninhbinhhuynh7619]

This is the best explaination about this problem, thank you so much 🙏

[@techdose4u]

Thanks :)

[@SHUBHAMYADAV-bs8vl]

Great explanation sir!, I find this problem difficult to solve, but after watching your video, it makes me easy to solve.

[@techdose4u]

Thanks

[@ganavin3423]

Thanks .it helped me understood

[@beaglesnlove580]

This was amazing description thank you

[@TheBaljitSingh]

it was a great explanations video. i finally understand the #concept

[@FOODASMRFAMILY]

amazing explanation with diagram approach

[@shriyasonam2716]

beautifully explained!!!

[@stoicbro1635]

beautiful explanation

[@brijvaghani6212]

Very well explained 🤜

[@kaushikramabhotla4635]

Maja aagya sir 🙌

[@techdose4u]

Thanks 😊

[@handlerhandle123]

Graph helped thank you

[@techdose4u]

Great ❤️

[@outsider9633]

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

[@maksymmoroz]

Thank you man, you helped me! Very clear

[@LalitPandeyontube]

such a great explanation

[@ullasbc728]

Good Explanation! Thank You

[@tridoan7383]

Great explanation

[@mahipalsingh-yo4jt]

This channel saves me everytime:)

[@techdose4u]

❤️

[@rajatgoyal8155]

Best explanation for this problem....👍👍
Thank you so Much for such a detailed explanation...🙂

[@techdose4u]

Welcome : )

[@radhasingh3549]

Amazing explanation😍

[@Karanyadav-cd4sq]

rather than sorting we can reverse it, so making the complexity go from o(nlogn) to o(n)

[@rushikeshkulkarni1784]

What if we get peak at 0th index but other half is not sorted..
eg. 3 1 2

[@kasturisanyal6649]

The explanation is so good and every detail is covered throughly. A hard problem made easy. Thank You so much:)

[@techdose4u]

Welcome :)

[@hridamchakraborty6818]

thank you so sooo much.. the explanation is great ..

[@techdose4u]

Welcome

[@praveengautam4689]

genius...:)

[@MrChetan54]

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

[@gokulnaathbaskar9808]

Thank you, Sir, this was nice

[@gauravraj2604]

Great explanation. Thanks a lot

[@quirkyquester]

you're the man broo! Thx!

[@techdose4u]

Thanks 🙏🏼

[@sujalhansda8285]

Brilliant !

[@amitmohapatra292]

can anyone tell me what kind of questions is this i mean under which concept is it coming ?

[@shubhamchavan1387]

Thank you!

[@techdose4u]

Welcome

[@codingnightmares3407]

Thanks a lot!
Best explanation 🧡

[@techdose4u]

Welcome

[@ishwaripednekar5164]

Really appreciated ❤️

[@techdose4u]

Thanks :)

[@gautam4696]

Bhai you are the best

[@techdose4u]

Thanks :)

[@waliullahsiam7999]

thank you so much for such a beautiful explanation may god bless you

[@satyanarayanagokavarapu3011]

Can you explain Integer to English words leetcode 273 problem ?

[@techdose4u]

Sure. It's very important for FAANG :)

[@satyanarayanagokavarapu3011]

@@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.

[@techdose4u]

Sure

[@gokulnaathbaskar9808]

This was beautiful, thank you

[@chiragPatel22c]

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 👍👍

[@samakshtandon1190]

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].

[@shivamagrawal3542]

What is the time complexity here?

[@avert_]

nlogn

[@Purubro]

Level ka observation h vaiya

[@formulaire.8379]

why we dont just use next_permutation ?

[@ghanishsingla8270]

Code link doesn't work, getting 404.

[@anubhavsethi7728]

Well explained 👌🏻👌🏻💯💯

[@techdose4u]

Thanks

[@user-jp9jd6el1f]

Sir plz apni facevalue bhi banaaiye

[@ShivamGupta-cx3hy]

Awesome Teacher

[@techdose4u]

Thanks

[@KarthikNandam-xs4qn]

Amazing 🤩

[@techdose4u]

thanks :)

[@tech_wizard9315]

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)

[@iamparitosh]

The only secret to nailing Linkedin is to be successful in real life. Do extraordinary things only when that will happen; No shortcuts whatsoever

[@tech_wizard9315]

@@iamparitosh along with good work, if you customize your account to make it look more presentable, it can help too!

[@coder1015]

Amazing ;)

[@techdose4u]

:)

[@qazaqempire3828]

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

[@andriidanylov9453]

Appreciate

[@themountains1701]

It's not working.

[@GeetainSaar]

Better than striver

[@takumisugita936]

medium btw

[@karmakaraayon4238]

Found a mistake 12:51 [2,4,3,2] -> ngs is not [2,4,2,3]

[@ECBBHAVYASREESUNDURU]

The peak element here is 4 . ig we have to swap 4 with 2.

[@nishant5249]

At 4:30 your explanation is not correct... If you check the striever video explanation then you can spot the mistake

[@rhs1078]

Worst explanation ever

[@saikatpaul6576]

how did you rearrange the next greater sequence, its confusing as I am not understanding whats the next greatern sequence means

[@manojjain3501]

Minimum of all greater permutations of given number. Ex 1386 -> Next minimum should be 1638 ( It is lowest of any combination of greater permutations )

[@rangdeb]

amazing explanation

[@techdose4u]

Thanks :)

[@bhuvneshsingh3347]

Thanks!

[@techdose4u]

Welcome 😀

[@rohithalder7546]

Great explanation

[@azharuddinkhan1865]

Great explanation