for the first time here this is world's most in-depth course when we talk about Dia Salvo why do I say that 455 this course is 455 modules by the end of the post it I sold more than 400 plus problems when it comes to DSL go you can go over the entire internet you can buy any of the paid courses in the market none of them will be teaching you DSL go in such step something that I can give you as an assurance is once you complete this entire course you can create any of the DS algorithms in any of the companies in any part of the world so till now we have covered till this particular problem and this video I'll be covering the problem rotate matrix by 90 degrees so this problem also goes by the name rotate image and what does the problem State the problem States you'll be given an N cross n Matrix so that is a square Matrix so imagine here given the square Matrix your task is to rotate it in the clockwise Direction by 90 degrees so if you rotate it in the clockwise direction right 90 degrees this is what you will get and this is what you have to print that is what the question States so this question comes up in an interview the first solution so this question comes up in an interview the first solution that you'll give to the interviewer should be of the Brute Force solution and what is that so you are given a matrix of n cross n size so what you will do is you will create an answer Matrix of n cross n size and that is where you'll store the answer so what you'll say is you'll pick up one and you'll try to place it at its correct place you'll pick up two and then you will try to place it at its correct piece pick up three place it at its correct Place pick up four place it at its correct please pick up five place it add its correct Place 6 as per X play 7 8 then 9 then 10 then 11 then 12 then 13 then 14 then 15 then 16 and then this is your answer and this you can print out so how do you place all the elements at its correct place so to do that you have to do some observations so can I say the first row always goes to the last column it does the second row always goes to the second last call of Midas the third row goes to the third last and the fourth row goes to the fourth last call this is something we can definitely observe so what I will do is in order to map in terms map it in terms of indexes I'll try to write the row index and this is how the row index will be always starts from 0 and since the size of the Matrix is 4 last one will be 3 right and the column index will be 0 1 2 3. so this is the normal indexing in a 2d Matrix now let's try to map it so can I say the one who is that the zero zero index is always going over here which is basically 0 1 2 sorry 0 1 2 3 and away one two three so can I say the zero zero always goes to the 0 3 I can and can I say if this is done then guys over here it's 0 1 who always goes to over here which is 1 3 can I say the zero two which is this one always goes over here which is 2 3 let's try to observe after this and then can I say 0 3 which is this one goes here which is three three so this is something which I've done for the first row now let's try to do for the second row so can I say one zero which is 0 to perfect then can I say one one goes over here which is one two then can I say one two goes over here which is 2 2 can I say over here this is one three which goes over here which is 3 2. now let's try to observe something so I've written for a couple of rows and assume you are traversing in The Matrix in this possible way and this is the generic way to Traverse in The Matrix and for Traverse earlier using IE and J index now this I is 0 this J is zero where is it going let's try to map it in terms of I and J itself so can I say this is 0 this is 0 this is 0 but this is one so I cannot find any matches but do You observe something whatever J is the same thing is on the row over here so can I say this J goes to this jig I can and similarly you can see over here this J goes to this J Duo observe that this J is also going to this one U2 but how do you map this one because over here it is zero zero zero over here it is three three over here it is one one one it is 2 2 but do you see something yes it's constant this is also constant so something I can see is for 0 for the zeroth row it is going to the third one which is basically this and for this first it is going to the second so can I say if this is I it will be n minus 1 so this is the last index because n was 4 so this is the last index and can I save it as 1 which is I this is n minus 1 minus I can I say this yes I can because if it is 1 just write if it is 1 1 goes to n minus 1 1 so 1 goes to n minus 2 N is 4 so this overall becomes 2. so can I see the formula is if it is I the other one will be n minus 1 which is the last index minus I very obvious because if it is 0 this will be n minus 1 minus 0 which is n minus 1 which is 4 minus 1 which is 3 very simple so I will always go to n minus 1 minus I so over here I can say this will be n minus 1 minus Pi simple as that and this is what it will be for every i j you put it to J and N minus 1 minus I and that is the Brute Force so how will the Brute Force code look like what I will do is I'll declare an N cross n answer Matrix which is going to store D and so then I'll start iterating from 0 to n then the inner loop will start iterating from 0 to 1 again and this will make sure that I Traverse the entire Matrix uh element by element now what I'm saying is in answer of J n minus 1 minus I I will put whatever is in The Matrix of i j whatever is the element i j it will always go to this place and that's it and I go to every element i j and I put it to its correct place in the answer So eventually this particular answer array will be created and we can return so the time complexity of this particular approach is we go of N squared and the space complexity of this particular approach is also big of n Square because we are using an external 2D Matrix in order to store the answer now this is where the interviewer will not be happy because we are using an extra space and will ask you to optimize it now as the interviewer is not happy with the Big O of n square space that we are using that clearly tells us that we have to solve this problem in place what does in place means it means that you have to solve it within the given Matrix itself we cannot use an additional Matrix so how can we solve in the given method text itself so the first observation is the key let's try to observe something can I observe one thing now the first problem is over here it is but it's in the reverse order it's in the reverse order if you see it's like 3951 and if you again carefully see the second column is over here but again it is in the reverse order like 2 6 10 40. even the third column is over here but it is in the reverse order and this is the observation that will help you to solve it so it's very simple what you do is you say let's transpose The Matrix why you'll understand very easily so you know what does transposing of Matrix means it means the column becomes the row and the row becomes the column that is what transpose means so one five nine thirteen will become the row so let's write one 5 9 13 becomes the row then this one will become the second row so it'll be like 2 6 10 14 next this one will become the third row 3 7 11 15 next this one will become the fourth row 4 8 12 16. so we did transpose the given Matrix and if you carefully see the First Column is now the first row and the first row is the First Column and similarly the second column is the second row and the second row is the second column over here so we have successfully transposed the Matrix and now if you see it's 3951 so it's the reverse of this now what you will do is you will reverse every row you will reverse every row so if you reverse every row so this is 1 5 9 13 reverse it so you'll get this this is 2 6 10 14 reverse it you'll get this this is 3 7 11 15 reverse you get this so why did we do the transpose it is a very simple reason because 1 5 9 13 this is the First Column and this was appearing in the first root yes and that is a sign that please go ahead and transpose it and then you can easily reverse because it's clearly visible so two steps first transpose The Matrix then reverse every row if you do this it will be done in The Matrix itself without using any extra space so we know that our optimal approach is going to take couple of steps the first one is transposing of the Matrix and the second one is reversing every row but we need to First figure out how do we transpose something so let's observe this is the original Matrix and this is the transposed Matrix let's try to observe something we have a one and it stays over here we have a six it stays over here we are available it stays over here we have a 16 it stays over here so all the diagonals if you see zero zero one one two two three three all the diagonals on these indexes are staying wherever they were so the diagonals will stay wherever they were so what I'll do is I'll try to probably draw a length for the diagonal so let's draw our remain for the diagonal now which are the things that are not staying at their place it's red also we have a two we have a five and if we carefully see they are sharped places okay perfect so can I say the zero and one index okay this is zero this is one so this is the two has gone to the one zero index can I say this one to one and zero I can next we have a three and we have a nine let's observe what has happened to them we have a 9 and we have a three so they have swept as well so can I see the 0 2 has gone to two zero if you carefully observe because this is 0 to sorry my bad this is 0 2 and this is 2 0. so we did see that 2 did have a three data have a side let's look for four so if we look for four look for 13 can I say again the same thing has happened yes it's like 0 3 has swapped to three zero okay we can see that everything in this column sorry this row got solved with everything in this call done next we have a seven right we have a seven and we have a ten so again they accept Okay so 7 is at one two and it got strapped to one interesting next we have a eight and where did eight go over to fourteen if we carefully C it does so can I say we have one three this time going over to three one perfect so first row down with the first call next we have a twelfth so can I say 12 is that two three and that goes to 3 2. which is this so again the second row will be done with the second column Do You observe something every indexes rather every index goes to the Opposites like 0 1 will go to 1 0 1 2 will go to 2 1 2 3 2 3 will go to 3 2 opposites and we just have to travel store the right half and we have to look at this for the zeroth row you have to travel in one to three so for 0 you have to travel from 1 to 3. for the first row it returns from 2 to 3 observe something for 0 you traveled from 1 to 3 which is meaning like can I say if it is I this is I plus 1 and this is n minus 1 yes because for one you've traveled from two to three so if this is I this will become I plus 1 and this is the last index which is n minus one so if I have to write a pseudo4 can I say we started from 0 and we went on till 2 because that is where our last element was so can I say I will start from 0 as I and I'll go until n minus 2 index not n minus 1. we will not go on till last we'll just go on till second last and the J where is the J starting in from if you carefully see this half is this half of the Matrix will always start from one element head which is I plus 1 so I plus 1 and it will go until the last and over here can I say it will be a swap of a of i j comma a of j i very obvious and if you swap them you'll actually get your transpose Matrix so once we have transposed the Matrix we will have something like this what was the step two of the optimal approach pick up every row and try to reverse it so if you reverse every row you will ultimately get your rotated Matrix and that will be your answer so let's come back to the editor and try to code it up in case you want to try out the problem please do consider trying out the problem from the link in the description so what is the first thing let's find out the size two steps transpose and reverse so let's perform the first step transpose it's like going from here till the second last and we only travels in the first half so we will be going something like from here to here and G plus plus and it'll be saying swap of mat of i j with man of J X so we just sharpened so the step one is done well the step two reverse every row so every row is basically in from 0 to n minus one so we go from here to here and we try to reverse every row so what is every row can I say every row is basically mad of C matter by that's the row so we say reverse of modify since it's a vector we shall begin and we say modify Dot N in case your language doesn't have a reverse function what you can do is you can use this method where you take one one sharp then you take the next strap then you move so it's basically a two pointer approach I will be leaving the article Link in the description you can go ahead and try out the small function which reverses any given array in Big O of n by 2 complexity so this is how you will reverse it and ultimately you can go ahead and try to run it up I think it should be running fine it does and now we will quickly sum it up so what will be the time complexity can I say this is basically traversing one half of the array so I can say it's basically n by 2 that's what the first Loop runs for and the second one nearly runs about ny2 okay so it's like n by 2 into n by 2 for the transpose what about the reverse can I see it's basically running for n for all the rules and then we are reverse it and we did C for reversing we can just use the two pointer approach which basically reverses till going half of the array so can I see the internal group plans for n by 2. so this is the overall time complexity this plus this are we using any extra space now we are doing it in place so we are not using any extra space in order to solve this particular problem so coming back to the sheet I can say that this particular problem is also done and if you have understood everything about this video please consider giving us that like because it won't cost you anything but it will keep you motivated to make these kind of videos and if you're new to our Channel what are you doing hit that subscribe button right away and if you haven't followed me on Instagram LinkedIn and Twitter you can find all the ID links in the description with this I've been wrapping up this video let's read in some of the video until then [Music] I will find the light in