Leetcode 503 | Minimum Operations to Sort a Permutation | Q3

Added: 2026-05-25

[00:00:01]Hey guys, welcome to recent contest.

[00:00:03]We'll be discussing problem number three. Let's get started. So basically you are given an array. Uh you're g a permutation right and you can do two operations either rotate by left rotate one by left or you can reverse the array. Okay. So the main idea is this is observation based problem and uh we will start from reverse. So imagine that you have the array is already sorted and you want to reach the input state right.

[00:00:38]So input state we could do two operations rotate by left or reverse. So in order to go go from the sorted state to the input state you can rotate by right rotate one rotate by one right or you could reverse right. So yeah, so we just mirroring the operations just to get from your we just thinking backwards basically. Okay. So now the idea is to see what kind of arrays you can reach. So if you are given 1 2 3 4 5 then let's say we rotate by right we two by right like you move two places to the right. So right rotation is like two times like this. So like the first one will give you uh 5 1 2 3 4 I think right and then the second one will give you like I don't know four uh yeah 4 5 1 2 3 right yeah and then let's say you reverse this array let's say you reverse this so now your array will look like 3 2 1 5 4 okay so that Main trick and the main observation here is that you need to keep your eyes on this one like where is this one going and how it is behaving.

[00:02:02]So after you did this right operation like rotated by two what happened was your one landed here but it's still there's still a wraparound characteristic with this one. So it's like you are still able to sort this arrow in some way. So you are able to go to 1 2 3 and then all the way from three you're able to go to four and five right so there's this wraparound behavior wrap around behavior which is always preserved preserved yeah and this you can this observation you can only get after doing a lot of examples let me be very clear so that's what I did like this this is my drawing when I was actually solving the problem and that's when I figured out yeah this wrap around behavior does exist and it's pretty easy to see after you know you're after playing around with it a little bit. So even after reverse this wraparound behavior will just get shifted to the left. So here you're wrapping around from the right because you're going like 1 2 3 and then yeah wrap around four five but here after reverse it's going to the left 1 2 3 and then wrap around four five. Okay.

[00:03:18]So, and let's say you let's do one more right rotation. Then what you'll get?

[00:03:23]You'll get uh like four 3 2 1 5. Right? So the wraparound behavior is still preserved. It's still going to the left now instead of the right. And if you reverse it, if you reverse this array, uh you get like uh 5 1 2 3 4. Right? So now the wraparound has mirrored it. It goes to the right.

[00:03:51]So one observation here is your array will always has to wrap around either to left or right. Okay. And if your array doesn't wrap around then there's no answer. I mean you cannot sort it.

[00:04:10]Right?

[00:04:11]So basically now going from 51 23 4 to your sorted array originally is very easy. You could just follow the same steps in reverse probably, right?

[00:04:22]Okay. So after you are done figuring out this wraparound observation, this is your start observation. Now you want to actually solve the problem, right? So there are two things now. Um so let's say you are given this array. Let's say uh you are wrapping around to the left 5 1 2 3 4. Okay, let's say this is the array and you want to make this 1 2 3 4 5. Okay. What can you do?

[00:04:48]You either rotate by left to the one like rotate once by left to get 1 2 3 4 5 in one operation. Pretty easy, right?

[00:04:58]Just left and or or what you can do is you can reverse the array. You can reverse the array.

[00:05:11]Uh reversing will give you 4 3 2 1 5.

[00:05:16]Okay. And then you by reversing you change the wraparound characteristic.

[00:05:23]You flip the wraparound characteristic.

[00:05:25]Initially the wraparound characteristic was towards the right. By reversing you made it towards the left because now you're going 1 2 3 4 5 1 2 3 4 and then you're wrapping around to five. Earlier you used to do 1 2 3 4 and wrapping around to five but it happened from the right. So we reverse the array and now we do all left rotations. All left to get one in place.

[00:05:51]One in place. Okay. So now it's just the index of this one. So after reverse its index would become like if you have element like one is at I then it would go at n minus i minus one. So here in this case it is at 0 1 2 3 at the third position. So that means that you just need to do three rotations to the left.

[00:06:14]One 2 and three. So we need to do three left rotations.

[00:06:20]That's it I think. Right. 1 2 3 4 5 to get your like oh okay. So after so sorry after you do three L rotations your array will look like this. uh you you get 15 um I don't know what you'll get 154 32 maybe right and then you do one more rotation one more one more left to get your arrow in reverse 5 4 3 2 1 Okay then you do a reverse operation to get 1 2 3 4 5 this is another way to do Okay, this is another way to get your array. So either uh so so the default rule here is that if your array wraps to the right as we saw here it's wrapping to the right. Then what we can do is that there are two choices. You have two choices either.

[00:07:36]So yeah, one is lying over here somewhere and it's flapping to the right. So it's easy to like just rotate all the way to the left from the index.

[00:07:47]Let's say one is at I. So you can do I rotations to the left. So I rotations to the left. Or you can reverse your array to make it wrapper on the right. So or we can spend one operation reversing it.

[00:08:03]So then your array would let's say look like this uh one and it's wrapping around to the left now right as we saw here in this case.

[00:08:17]And then and then after reversing you you have this one at n - i minus one position right. So you rotate left by n minus i - one. So what you get is you get one and then like uh 2 3 4 5 x we got this right. Yeah.

[00:08:45]And now we do one more left plus one reverse.

[00:08:53]So what you get is you get 5 4 3 2 1 by doing one more left plus reverse you get 1 2 3 4 5 again in this sorted array. So now if you count this path you're doing how many operations?

[00:09:07]doing 1 + n - i - 1 + 2 2 because one more left plus one more reverse. So what is that? This number is n - i + 2.

[00:09:20]Okay. So it will be the minimum answer will be the minimum of these two because you can do i or you can do i + 2.

[00:09:29]Let's take the minimum of i and n minus i + 2. Okay. Yeah.

[00:09:36]And similarly we have to think of the case where uh the array was like originally wrapping to the left wrap to left.

[00:09:49]Okay. Yeah.

[00:09:53]I minus I. Okay. So wrapping to the left. Um so like you have one and it's wrapping to the left like this.

[00:10:06]Okay.

[00:10:07]So for example, you have the array like this. 1 2 3 4 5.

[00:10:14]Yeah. So what you can do is you can uh let's say you reverse this array, right?

[00:10:21]So that it wraps around to the right.

[00:10:24]Um or let's say let's do the simple thing first. Let's let's drag this one all the way to the end. Okay. Um yeah, you cannot do that. Sorry.

[00:10:39]So what you can do here is let's let's try to you know um I don't know let's try to do what we did here I guess right it's if it's wrapping uh to the right we did a wrap to left by reversing it right so you spend one operation reversing it so we are standing at this position with our index i over here right? So we know that if we are standing at I here then we just we just need to follow these sequence of steps. So what we need to do is we need to like rotate left by this. So uh you you get this array 15 4 32 and then you get one more left plus one more reverse. So 5 4 3 2 1 and then you get 1 2 3 4 5. So how many operations did we do? We did um I operations to get one here. So I is 012. So two ops to get this + 1 + 1. So how many did you do? We did I operations + two, right? I + 2 operations.

[00:12:05]And there is still another way you can do it. You can now wrap to the right by reversing it once. Right?

[00:12:16]So now we are playing symmetry. So web to the right by one reverse operation you get this array you get uh one but now it is at n minus i minus one and now this guy is wrapping to the right. Okay.

[00:12:33]Yeah.

[00:12:36]Yeah.

[00:12:38]And since it is wrapping to the right what can you do?

[00:12:45]You can simply you know just do like I operations maybe.

[00:12:53]Uh so your array now looks like so earlier it was 32 54. You did a reverse.

[00:13:01]So you you got 4 512 3. So this is web left. Now this is to right. And now you just pull this guy all the way till the start. Okay. So you get uh n - i - one operation has to do it I guess right. Yeah.

[00:13:26]Uh yeah I think h n minus i minus one operation has to do it. So if you do 1 2 3 uh 4 5 4 5 1 2 3 Okay, plus one reverse, right? Plus one reverse we did in order to wrap. So you get n minus i operations.

[00:14:02]So you take the minimum of these two now. Okay.

[00:14:08]And I think we can also explore the other case where we since we wrapped to the right um we can like I don't know we can also consider reversing it again and wrapping to the left basically this branch but then that would increase the number of operations because why would you reverse it again?

[00:14:29]like reversing it again would wrap to the left and you're stuck at the same problem. So yeah, these are the only two possible operations that you can do. I + 2 and N minus I. Okay.

[00:14:43]Yeah. So pretty fun problem.

[00:14:47]That's my I mean the code is pretty simple. Now we just check if it is rotating wrapping either towards the left or the right using these two blocks.

[00:14:56]Right? If neither of them are happening then minus one. Else if let's say okay one is basically wrapping to the right.

[00:15:04]So it's minimum of I comma N minus I + 2. Yeah. So this one I comma N minus I + 2. OG ID is basically I the original ID of the minimum index. Right.

[00:15:19]And else it is N minus I and I + 2. So yeah, n minus i and i + 2.

[00:15:30]Okay, cool. Uh that was the video. Thank you guys for watching. and pay.