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

Key Takeaways

All right. So in today's problem, we are going to look at the problem next permutation. How do we generate the next permutation given a sequence that we already have? So if our sequence is 1 2 and 3, the next permutation in that sequence is going to be 1 3 and 2. If I have 3 2 1 as my permutation that I'm given, the next permutation in the sequence is the first permutation because this is the last permutation of the numbers 1 2 and 3. This is the last permutation. So we just return the empty array. There is no next permutation. 1 5 and 2. What is the next permutation? The next permutation is 215. When you're looking at these, you might not see a pattern. And I myself, I do not see a pattern. But we do not see a pattern until we understand how permutations are built. All right. So we have two choices to this problem. We first we can generate every single permutation until we hit the permutation we are given and then we go one step forward. That will give us the next permutation. The problem with that approach is we're going to be doing factorial time work. n factorial* n whatever work we're doing in our base case or our individual calls but we are going to go through at worst n factorial permutations if we're given the last permutation and this is a very expensive way to go about things. The point of this problem is not to have you brute force it like this. The point of the problem is to see whether you really know how a permutation is built and whether you can do a in-depth case analysis. If you have not seen my video on building permutations and permuting a string, I highly recommend that because that will help you a lot with understanding what goes on here. But let's investigate now. Let's start connecting the dots and see how is a permutation built. So if we're given 1 2 and three, what we need to do is we need three slots. The point of a permutation is to exhaust the possibilities of placing each one of these letters in a slot and then recursing and then placing the rest of the numbers. So here's an example. At the first position, we have the choice of placing the one, the two, or the three. When we're doing it like this, temporal order gets preceded. So we're going to place the first item, the least item, which is one. So I want you to notice something. One is not in our possibility space. We are at the second slot. We only have two choices. We have two slots. We have two choices. And at this second slot, we can either put a two or a three. We can either put a two or a three. Notice that. So what you see here is we planted a one. And that's exactly where our permutation stands in its state right now. They decided to plant a one. And notice they decided to plant a two. So at this position, we either could plant the two or three. The decision was made by this person or however this permutation panned out to place the two. At this position, at this state, it holds a state. It is currently exploring the number of ways it can place two and then recurse. We place the two and we explore all possibilities. And then after we place the two, our decision space is down to three. Now all we can place here is a three. Let's place the three. And now we have exhausted our decision space at this slot. All we could place is the three. So now we ask ourselves the question. We ask ourselves what is the next permutation to 1 2 3. Now do you notice how we understand more about the problem? we understand more about the state that the permutation we are sitting in came from. Where did it derive from? What state is this slot in? This slot is in the state of exploring the placement of two. Notice that we have exhausted all the placements. All we could place here is three. We've done three. So, what we need to do to find the next permutation is backtrack one. Okay, we backtracked one. And again, we're going to get to the core algorithm, but I just need you to understand this walkthrough. So, we got through the three and now this slot is empty. Three is back in the decision space. And notice we planted on two. We explored all of the possibilities that two's placement had to offer, which was placing a three here. And now two has exhausted itself. And the two returns to the decision space. So now we can use either two and or three at this position. The next thing to place is going to be a three. Before it was two. Two did all of its exploring. This was on its last permutation. And now we place the three. And now notice three is not in our decision space anymore. And now all we can place here is two. And so now 1 3 and two. So what is the overarching state? The overarching state is we planted a one. What else could we have planted here? We could have planted two or three. So all the while we're doing our exploring over here, we are doing it off of the planting one. While we're doing our exploring here, we're doing it off the planting three. While we're exploring here, we're doing our planting off of two. It is all about planting and exploring possibilities. So this is the next permutation. So let me ask you, what would the permutation after this be? So what we notice is that a section that is decreasing has exhausted itself and reached its last placement. If we try to find the next permutation, what we would do is we would need to see where we need to backtrack. So what we do is we notice the two has exhausted all of the possibilities. So we need to erase two and return it to the pool. And notice we have no more things to explore at the second slot. We've tried the two, we've tried the three, so we erase the three. And so now we have explored all of the possibilities with one rooted in the first slot. Now what is the next item to get rooted? Two is the next item to get the rooting. And now our decision space has adjusted itself. Two gets the planting. We are now exploring on two. And now we have two choices for the second placement. We can place the one or the three. And now we choose precedence on the lesser item. So one gets the placement. And then all we can put in the last slot is three. That's all we have left. So this is the next next permutation. This is the permutation after the permutation we just made. So I want you to start noticing a pattern. What we're doing is we're looking for a strictly decreasing section because that is the section that has exhausted itself. This has exhausted itself. So this would get erased. So the element before the strictly decreasing section is the element that still has options to explore. So now the next option would be to explore the three and then so on. So what we notice is the item right before a strictly decreasing section is the item of interest. That is what we need to do our modulation on in order to advance us to the next permutation because the strictly decreasing section has exhausted itself. the item before that section has items that it can swap between. It still has more choices for its slot. So, let's look at a concrete example to see this pattern. So, this is a very tricky case analysis problem. This is not something where you just instantly know the answer. And I need you to make a few intellectual jumps here so that you can really let this sink in. So, what we just noticed is each of the decisions are plantings. So imagine I am given this permutation. We'll see why these are important. But notice this person said let me plant six. It goes out of our decision space. They said let me plant two. It goes out of our decision space. They said let me plant one. And then one disappeared from the decision space. But notice here this item is before a strictly decreasing section. Remember we just established a strictly decreasing section is on its last permutation. If this section is on its last permutation, what do we need to modulate? We need to modulate what is right before that strictly decreasing section. Why? So when we are at slot number three, we have these choices. We already expressed all of zero's decisions. If we are on one, if we chose one to be placed in the slot, we have passed all of zero. Zero is behind us. That's not going to be on our next permutation planting. We need to consider what is the next item that we planned here. So these are the items left to us that were cut out of our decision space. So we have a 1 3 4 and a five. And notice our one is the item that was chosen. So the next item to take one's position. The position right before the strictly decreasing section. The item is the next greatest item to the right of one. What is the next greatest item? The next greatest item is three. So, we look for the item that is the next greatest item in the decreasing section. We look for three because guess what? Three is next up in line to get the placement at this slot. And then four will get a placement and then five. So, what we do is we swap these items. We swap the one and a three. So, that three gets its placement. It is next. Okay. So now we've almost completely simulated going to the next permutation. We've swapped the next rooting before the decreasing section. But notice that this is on the last permutation if we were going to plant at three. So what we need to do is turn this strictly decreasing section into an increasing section. So we are on the first permutation of planting at three. This would be the last permutation planting at three. We want to be at the first permutation planting at three. So we reverse this sublist. We don't need to sort it. We can just reverse it because it's already in reverse sorted order. And so now this is how we find the next permutation. Notice we've only done linear time operations. We're not going into factorial time complexity. We've been able to use case analysis to stay linear in how we solve the problem. So three got its next rooting and the suffix has been minimized. When it is decreasing, it is maximized. It is on the end of itself. But when it is increasing, then we have minimized this. We have minimized the rooting. And guess what? This is the next permutation. And that is how you find the next permutation without using factorial time or expanding a brute force solution. And so now the time and space complexities are very straightforward. N is the length of the permutation string we start with. So the time complexity is going to be O of N. We're going to scale in a linear fashion as our input gets arbitrarily large. This is because all we do is linear time passes. We're going to do a linear time pass to find the longest decreasing sequence. We're going to do a linear time pass to reverse that sequence. And we're just going to do a constant time swapping. So none of this is going to take us past linear time. For space, we're going to stay constant. So the reason it's constant is we're just going to be using local variables. We're just going to be using pointers. We're not going to be using anything that scales our space as the input gets very large. So these are the time complexities. So if you like this video, hit the like button, subscribe to the channel. I hope this explanation was as clear as possible. This is not one of those questions that scales well to other questions. It's really one of those things where it's a raw case analysis and really understanding the backtracking of permutations to be able to analyze a solution like this. It's not something that is going to apply for many things. So that's all for this one and [Music]