Compute The Next Permutation of A Numeric Sequence - Case Analysis ("Next Permutation" on Leetcode)

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a permutation of a sequence, calculate the next permutation in that sequence (if the permutation given is the last one, just return an empty array since it has no next permutation...it is the last permutation).
Approach 1 (Brute Force)
We can compute all permutations and stop on the permutation right after the permutation given.
This can have us generate n! permutations in the worst case (the permutation given is the last one).
Approach 2 (Use Intuition & Patterns)
Permutation Sequence Example:
[0, 1, 2]
1.) [0, 1, 2]
2.) [0, 2, 1]
3.) [1, 0, 2]
4.) [1, 2, 0]
5.) [2, 0, 1]
6.) [2, 1, 0]
This approach will use the idea that we notice patterns.
Notice how we plant the 0, the 1, then the 2 in the first slot as we go through the sequence.
Also, notice how the last element is the array completely reversed.
These may not matter but we are just piecing things together right now.
Let's formulate a plan.
[6, 2, 1, 5, 4, 3, 0]
We know to get to this permutation we
rooted 6
rooted 2
rooted 1
If you remember back to generating permutations it was all about planting items and then picking from a pool of remaining items.
When we plant 1 we have a pool like so [5, 4, 3, 0].
Remember how the last permutation was the original pool reversed? We will look for the longest reversed pool because we know that it is the last permutation for that particular rooting.
This is [5, 4, 3, 0] in the example given. This is a maximum suffix after the planted 1.
1 is of interest since this means we have exhausted the possibilities of permutations with 1 rooted where it is since it's suffix following it is strictly decreasing.
SO TO GET THE NEXT PERMUTATION WE SWAP 1 AND THE SMALLEST NEXT ELEMENT TO MINIMIZE CHANGE IN THE PERMUTATION.
We are considering back to the rooting [6, 2] which has a possible pool of [0, 1, 2, 3, 5]
0 got it's turn in index 2
1 got it's turn and is finished
SO THE NEXT LARGEST ELEMENT IN 1's SUFFIX IS NEXT TO BE PLANTED THERE.
Swapping yields [6, 2, 3, 5, 4, 1, 0].
NOT DONE.
Now the prefix has been advanced in the smallest way possible. BUT the suffix of our choice to plant 3 may not be the smallest it could be to be the next permutation.
NOTICE: The first permutation was in STRICTLY INCREASING order. We need to get our suffix in strictly increasing order
We don't need to use a sorting algorithm since that is expensive.
Remember, the suffix was in strictly decreasing order before, so all we need to do is reverse it and we will have a sorted suffix.
When you really grasp how permutations are made then this will make a lot more sense and you probably could get this in an interview.
Complexities:
Time: O( n )
We are just doing linear time passes through all of this so we stay linear in time throughout.
Space: O( 1 )
We just use a few local variables, our space usage does not scale as input size gets very large.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 6.10 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

[@BackToBackSWE]

Table of Contents: The Problem Introduction 0:00 - 0:55 The Approaches 0:55 - 1:58 Investigation: How Are Permutations Built? 1:58 - 7:47 Case Analysis: Deducing The Next Permutation 7:47 - 11:10 Time Complexity 11:10 - 11:42 Space Complexity 11:42 - 11:56 Wrap Up 11:56 - 12:21 The code for this problem is in the description. Fully commented for understanding and teaching purposes.

[@Official-tk3nc]

Some Useless channels are getting 10 million subscribers but useful channels like these are still in their 100ks . THIS PROVES ONLY a FEW PEOPLE ARE SERIOUS

[@BackToBackSWE]

lol nah it makes sense

[@vaibhavtiwari6540]

Knowledge never sells.

[@avinandanbanerjee9568]

I envy the intern you're going to mentor in a few years at Twitter. This was a brilliant and very lucid explanation!

[@BackToBackSWE]

thanks heh

[@vedantiyangar151]

Every one of your videos gives me a light-bulb moment. I always say a loud "Ooooooooooooooooo" when I actually understand how things work. You're on another level, Ben.

[@BackToBackSWE]

hahaha nice

[@shubhamchopra5518]

You make a hard problem so easy to understand! Keep adding more content. Thanks, Benyam!

[@BackToBackSWE]

sure ha, I'm taking a bit of a break from this channel and run a private class now. But I have a cool video coming soon

[@bahdjibrildjibril]

This is for sure my new go to resource. I love the clarity and the fact that you take the time to explain very well in details. I just feel like you explain this just like I need. Thanks so much again for the efforts.

[@BackToBackSWE]

thanks! check this out late July twitter.com/thebigoguide, it is the next leg of this project

[@abhishekthakur6612]

The way you explain is just awesome. The clarity in explanation and presentation , the way you emphasize on an algorithm is just too elaborative. Thanks. Love from INDIA ❤❤

[@BackToBackSWE]

thanks :)

[@watchClips661]

That's a brilliant way to approach the problem. Thanks!

[@animatedzombie64]

best ever explanation for this problem on the youtube.

[@ShivamShukla-uz9xs]

Thanks a lot for such a beautiful and intuitive explanation from the scratch and origin of the problem. How you drove the case analysis to the conclusion to solve the problem was really the awesome part. Thanks that helped a lot.

[@BackToBackSWE]

Sure.

[@DiaryOfMuhib]

The only video where I got an in-depth explanation. Thanks a lot.

[@BackToBackSWE]

ye

[@akashmittal5638]

This is the best possible explanation there can exist on this problem. I've seen lots of your amazing videos before, but this one is by far the best. I don't think I can ever forget this simple logic, thank you Ben!

[@BackToBackSWE]

Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@resetengineering]

This is hands down the best explanation. Watched a couple of videos which even claim to explain intuition, but they don't really. There were micro points in my mind that were cleared at each point of the video. Hooked me on to get through it with patience. Else I switch due to BS

[@BackToBackSWE]

thank you so much!

[@leonardocavalcanti1225]

Thanks a lot! Greetings from Brazil!

[@dochaar]

Benyam, thank you so much for your efforts. You have explained things in a way most people can't! There is a huge difference in knowing things and teaching them in a way to make others understand. You have certainly mastered that art. I once watched a video on youtube about linked lists by Dave Feinberg almost 8 years ago and till date it's imprinted in my memory. And, I pretty much solved any linked in question after that. Your explanation is definitely as good as it! I have a seen a few other videos made by you, especially the one on bit shifting (adding two numbers without using add operand). I became your fan after that! Thank you so much sir! Keep doing what you do the best :)

[@BackToBackSWE]

much thanks, all the best

[@snlagr]

i like the yellowish color tint of this video. Kind of soothing to watch.

[@BackToBackSWE]

lol - it was a mistake

[@atulmalakar]

I am in love with your explanation! ❤

[@BackToBackSWE]

thanks

[@deepakprajapati2635]

great explanation, I hate those videos in which they first write code and show how their code works. I like the kind of videos made by you

[@nelsonthekinger]

Impressive explanation! A "Real Intellectual Jump"! I was bubble sorting the right side for no use! Thank you very much, this is star quality material!

[@BackToBackSWE]

sure

[@hritiksaroj3147]

Would love to see some design questions on your channel!!!Btw Awesome explanation!!

[@BackToBackSWE]

will do

[@shubham_sinha1]

My goodness .....what an amazing explanation !!! U make any problem so so easy ......I saw ur explanation video on kadane's algorithm and subscribed immediately!!!

[@BackToBackSWE]

great to hear

[@harshg7262]

Incredible explanation, I have no clue how any company excepts someone to figure this out in 45 minutes tho

[@yunlongsong4521]

Great video. The algorithm is easy to remember, but not understanding it completely could cause negative effect in an interview. Thank you for your intelligible explanation!

[@BackToBackSWE]

sure

[@janvisingla3746]

Thank you for the great content :) . I spent like 3 hrs on this ques watching many videos and wasn't able to understand at all and suddenly land at your video and i was like "WOW HE IS SO GOOD" .Thank you again from INDIA :)

[@BackToBackSWE]

sure from AMERICA

[@geesehoward8838]

great video and great explanation!

[@BackToBackSWE]

thanks!

[@vaibhavkumar4821]

Thanks and kudos for the on-point in-depth explanation for not so simple problem. Do you have any other recommended problems for exercise that revolve around the core idea explained in this problem?

[@BackToBackSWE]

generating permutations (the problem) is a good followup

[@vaibhavkumar4821]

@@BackToBackSWE Thanks :)

[@ec5988]

Takes a legend for me to leave a comment and you sir, are a legend

[@alexpena9927]

i came here for leetcode help, now I am rethinking my entire life because I did not notice the 3

[@BackToBackSWE]

ye

[@tenki_desu]

牛逼啊 English Translation: This is freaking AWESOME And this is the BEST explanation I have ever heard for the next permutation problem.

[@BackToBackSWE]

thanks lol

[@adhammohamedsaberhusseinos1641]

Thank you for this tutorial!

[@BackToBackSWE]

Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@teresamao222]

Life saver! Thank you!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@IsomerMashups]

I do not understand how on earth this is a "medium" question. It's like all the ones where there's a trick: all you're testing is whether or not the person knows the trick.

[@8Trails50]

bro i was legit yelling at my computer shit blew my mind

[@BackToBackSWE]

great

[@greentealatte2845]

thank you!!!

[@BackToBackSWE]

sure!

[@no5xx]

Awesome explanation dude. Would love to support your cause !!! xD

[@BackToBackSWE]

yo

[@xinyuwang185]

Thank you. This is a great explanation for this question..

[@BackToBackSWE]

thx

[@patrickzhang1961]

you are a great teacher!

[@BackToBackSWE]

thanks

[@mystryb345]

Bro your Are GOAT

[@BackToBackSWE]

thanks

[@armaanpathan1856]

Whenever I need to understand the logic of how things work in complex programs Step 1 youtube Step 2 Search Back to Back SWE ... and I live happily forever after 😂 Thank you for this great explanation ❤

[@slm76]

Well done, thanks!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@symbol767]

You're doing Gods work bro, especially with that video breaking down finding the permutations, that was legendary. Thank you man!

[@BackToBackSWE]

Thanks bud! try out some more amazing stuff in our 5 day free mini course backtobackswe.com/

[@liangtang2127]

amazing explanation! it really helps me understand what leetcode 32 wants me to do :)

[@BackToBackSWE]

nice

[@niwanshumaheshwari4534]

i guess it's 31

[@prachurjyabasistha4682]

This is the best explanantion for this problem!!

[@BackToBackSWE]

thanks

[@HanhNguyen-xx8qb]

You're amazing! Thanks for your explanation ~

[@Icix1]

Excellent explanation. This is a ridiculous interview question. Either you "know the trick" or you don't, even if you understand how permutations work. It's not a test of coding ability or computer science knowledge. Just another gotcha question that employers confuse with an IQ test. A good example of how out of control the leetcode interview culture has gotten.

[@BackToBackSWE]

Thx

[@Icix1]

@@BackToBackSWE

[@Hav0c1000]

@@Icix1 I agree with the sentiment here... awesome channel, dumb question....

[@Calisthenoob]

Nicely explained!

[@BackToBackSWE]

thanks

[@pin-kuanhsieh4886]

thank you!

[@alexhoffmann3002]

Great video; this is a bitch of a problem and you explained it very clearly.

[@4sky]

So algo is.. 1) find the decreasing section at the end of the array 2) the item before the decreasing section swap with the next biggest number in the decreasing section. 3) reverse the decreasing section.

[@BackToBackSWE]

yes, but make sure u know why, the pattern is simple, the why is deeper

[@pranaychandra8016]

Can anyone please me with the ques. Generation next permutation in which is a palindrome containing the same numbers.

[@BackToBackSWE]

ye

[@biikaaa.6540]

i love this guy

[@BrandonLandrumJeffries]

hero's don't always wear capes!

[@Joyddep]

Hell yea that was clear!

[@narihanellaithy7726]

I loooooove you! I was about to lose my mind! saw this problem in EPI and I was like wtf! Thank you :')

[@BackToBackSWE]

nice

[@DK-ox7ze]

Great explanation! However, this is a generic approach which misses a few edge cases. Like when the input is [2,3,1,3,3], the output according to this approach should be [2,3,3,3,1], but the expected output is [2,3,3,1,3].

[@nelsonthekinger]

When you solve this type of problems I think you earn the right of dating the interviewer

[@BackToBackSWE]

lol

[@harimlee2172]

My first comment on KZbin -- this is such a great explanation thank you so much!

[@BackToBackSWE]

great and thanks and sure

[@jy8887]

The best explanation I could find on the internet. I highly recommend this channel!

[@BackToBackSWE]

thanks

[@meiwenzhou7270]

Thank you for sharing this. The prompt on Leetcode is complete nonsense to me...and you only used a 12 min video to decode everything!

[@BackToBackSWE]

sure and great

[@james131418]

Very helpful!

[@BackToBackSWE]

sure

[@AlexTran]

This man is the most talented person I've ever watched on KZbin.

[@adityadhanrajtiwari]

You are amazing bro ,you make programming interesting. ☺️

[@BackToBackSWE]

ye

[@ruchiteshmalukani6416]

Awesome !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@BackToBackSWE]

thanks.

[@joepresing5053]

Good explanation. Stuck on this problem for a long time.

[@BackToBackSWE]

Yep. It is what I do.

[@JacobAbraham-twozerosix]

Thank you! For this... I struggled with this quite a bit... Just could not see the pattern.

[@BackToBackSWE]

sure

[@ariellyrycs]

I solved it this way, but in order to find the next smallest on the right i was thinking on doing a bs, but in my case i would make it too complicated because the numbers could be repeated. and it has to consider the first of them all, that means that we have to find the the next smallest by doing a bs and then do another bs to bring the first smallest successor on the right. it could've been done in only 1 bs but it would be too complicated and too much code and this is going to be still O(N) time.

[@BackToBackSWE]

what is a bs

[@ariellyrycs]

binary search

[@pmpiyushmittal1]

Ido not think it is possible to come up with your own solution in 45 min interview.

[@BackToBackSWE]

yeah

[@abhijitpatra5679]

Next Permutation means the next greater element within the array range. correct?

[@BackToBackSWE]

i said the definition I think

[@rajparekh08]

very very well explained.

[@nikitanagarkar1643]

great video

[@linarudashevski166]

what is the link to the permutation video referenced around 1:52?

[@BackToBackSWE]

Should be somewhere in the channel videos

[@harshitsaluja3493]

Can someone provide the code for the above explanation?

[@qb8908]

i think this solution is wrong, if the rest of is not decreased order, you can not just sort it to get next permutation

[@Kgp-ty5dk]

fantastic explanation! I implemented this two years ago. revised everything in 10 minutes and implemented again!

[@BackToBackSWE]

nice!

[@anonymousvine4105]

A slightly more intuitive way to think of it is that you’re given an integer, then your task is to find the very next integer greater than this one by only using the digits given. You want to consider the set of unused digits from right to left. For example 45321. Check the tens place, is 1 > 2? No. Okay, we’ve exhausted our unused digits, add 1 to the unused set, then backtrack to the hundreds place. Are 1 or 2 > 3? No. Add 3 to the decision space and move on to the thousands place. Continue with 5. Are 1, 2 or 3 > 5? No, so add 5 to the unused set and backtrack to the ten-thousands place. Is 5 > 4? Yes, so now we want to construct the smallest integer we can that starts with 5 and must use 1, 2, 3, 4. Stepping back, we see that 45321 would indeed come before 51234 if these were the only digits we could use to construct integers. The algorithm is more natural to think of if we go back to our grade school intuition of how to construct bigger numbers.

[@hardikjain_08]

since we would require the next element to be planted we would have to sort the array and that will take O(Nlog(N)) so the time complexity of the overall problem should be O(Nlog(N)) in my opinion what's your say?

[@AE-ql7vo]

Dude! You’re really talented in simplifying tough concepts. Thanks a lot!

[@BackToBackSWE]

sure!

[@aushoroup9735]

Nearly for 20 to 30 minutes I just keep thinking how to solve this question ? What should have I to do to get the next permutation ? And I end up with your channel . Thanks for making us better.

[@abdaa5579]

Thanks for explanation. You are a good teacher.

[@BackToBackSWE]

thx

[@jackfrost8969]

wow excellent explanation, finally it clicked after watching bunch of Indian videos😭

[@uHnodnarB]

Maybe the expected output for the leetcode question has changed, but the expected output for [3,2,1] is now [1,2,3].

[@मयंकपठानियाँ]

thanks I didn't even understood "lexicographical permutation" from problem but you explained it well.

[@zionhuang5993]

DUDE! Your explanation is best I have ever seen! Your thought about the process of permutation really help me. You have real talent.

[@BackToBackSWE]

sure

[@uselesvideo]

Thanks man I was struggling with this unable to find a pattern; is this a good interview question? this just looks very specific; only if one knows how exactly permutations work can they see the pattern and answer it in 45 mins or maybe I am too new.. anyways to find the smallest number larger than the number before the strictly decreasing sequence dont we have to run atleast O(len(decreasingsequence)) in worst case O(n-1) one more time making this O(2n); I know its still in O(n) but can we do better can we get the smallest number larger than a particular number in O(1) or O(logn)()without constructing a binary tree which would ultimately make it O(nlogn).. also I have been keeping away from recursion problems out of fear that recursion is not scalable when it uses large space complexity; what do you think about using recursive approaches to problems that cry out for recursion like paranthesis generator

[@BackToBackSWE]

I haven't replied to this for a bit, replying to close this out in my "unresponded to comments" feed.

[@jackwindensky5606]

I don't understand why the time complexity is O(n). Every time you move to the next leading digit, you search the suffix to find which number to swap with. Wouldn't that trigger a log(n)? O(n) as you move the cursor to the left and O(log n) for the search triggered every time you move the cursor? Time O(n log n)?

[@BackToBackSWE]

what do you mean trigger log(n)

[@mrboyban]

Stating the obvious is easy as such that 2+2 =4, but not really clear which path are you taking to add them.

[@neelmanivispute1122]

Thank you so much for helping out beginners like me. :) . Keep it up.

[@BackToBackSWE]

Sure, you will not be a beginner forever. Remember that.

[@varunrao2135]

Very Very clearly explained. Good shit

[@BackToBackSWE]

thx

[@ivanluchev7996]

This is the best explanation one could give for permutations. The build-up makes it really easy to put the pieces of the algorithm together.

[@mayanksharma-qv4qm]

dude you are amazing, you deserve a lot more subscriptions!

[@BackToBackSWE]

thanks

[@gautamkumarshukla3055]

Very good explanation , as it not only explains how to do it, but also tells underlying pattern for why to do it this way

[@abhilashgoyal2234]

For those who are not getting this logic in one go, please refer to code first, try to think the logic, build a picture in your mind ( very high level) and then see this video. Perfect

[@BackToBackSWE]

ye

[@prakharsingh620]

What an explanation man Great work

[@Adam-tz6gk]

Beautiful explanation right here folks

[@nickk5050]

wow great explanation, I figured it out along the way w/ ur leading discussion

[@szarusz]

A fantastic explanation. I knew this problem, I knew the solution, but I never understood it as deeply as I do right now.

[@BackToBackSWE]

great

[@master_persi]

How do we find the strictly decreasing sec by watching this video???

[@umapathybabu8397]

excellent video, made to understand the problem clearly. looking more from you. can you do some oo design questions?

[@BackToBackSWE]

sure

[@NoName-ef2gv]

Crystal clear. You are one of the best teachers on youtube. Thank you.

[@makingitraln]

You remind me of VSauce xD. Great vid btw

[@BackToBackSWE]

haha, now way, he is way cooler, smarter, and calmer