Understanding Spiral Matrix Traversal

Hi everyone and welcome to the complete DSA series in which today we are going to do one more important question of 2D arrays called spiral matrix. Now this is a very classical question of 2D arrays which comes in many interviews. So today we are going to do this in detail. Apart from this, if we want to learn any other concept of DSA, then we will get it available on this channel in this playlist. So let's start with our question. This problem is also problem number 54 available on Leetcode. We have a matrix given in this way whose size is m cross nk equal. For example, here our m value is 4 and our n value is 4. So, here rows are also equal to 4 and columns are also equal to 4. We have to travel this given matrix in a spiral way and store all its elements. Traveling in a spiral way means that first of all we will cover our top boundary from left to right. So, we will have elements 1, 2, 3, 4. Then we will cover our right boundary from top to bottom. So, we will have elements 8, 12 and 16. means as we go on each cell, we are storing its output in spirally. After that we will cover our bottom boundary, in which we will get elements 15, 14 and 13. And then we will cover our left boundary, in which we will get elements 9 and 5. So whenever we are traveling in spiral form, we don't have to repeat any cell. Now let's suppose we have covered our outer boundary, now we will cover the inner boundary inside. So again we will follow the same format that first we have to write the top boundary, then we have to cover the right boundary, then we have to cover the bottom boundary and then we have to cover the left boundary. So first of all we will have the top which will be 6 and 7, then we will have the right which will be 11, then the bottom which will be 10 and then when we go to the top, since we have already covered 6 here, we do not have to repeat it. So in a way this is our output which should be produced for this particular 2D array or a matrix. So we have to cover our given 2D area in spiral way in these formats till the time all the elements of our matrix are not exhausted. Till the time we don't travel on every cell of our matrix. Now we already know that we have to cover the boundaries of our matrix. So for boundaries, first we have to go to the top boundary, then to the right, then to the bottom, then to the left. Now whenever we talk about boundaries, we should always know from where any boundary goes to where. For example, if we talk about the first layer of boundaries, then this will be our top boundary in which we are going from the 0th column to the n-1th column and in which our row is number 0. If we talk about the right boundary, then here our boundary exists from 0 to m-1 in which our column number is fixed which is n-1. If we talk about the bottom boundary, then it is going from n-1 to 0 and in which our row is fixed which is m-1. And if we talk about the left boundary, then it will go from m-1 to 0, in which our column is fixed, which is equal to 0. So whenever we talk about any boundary, either a row is fixed or a column is fixed. For example, our row number is fixed in the top boundary, our row number is fixed in the bottom boundary. If we talk about column-wise left and right boundaries, then our column number is fixed in them. So can we say that we can take 4 variables to track this information? Whenever we talk about boundary, we should have row and column information. So to track this information, we can make use of four variables through which we can track different rows and columns. We are talking about our outer boundary, not the pattern logic. We are thinking in this direction, if we had to print top right bottom left, how would we print them? We could take variables for them, one would be our starting row variable, another would be our ending row variable. Similarly, one could be our variable starting column and one could be ending column. We know that in terms of our boundaries, our starting row will be 0 where our top boundary starts. So, starting row will also be 0 and starting column will also be 0. Ending row, i.e. where the bottom boundary is, that is equal to m-1 and ending column is equal to n-1. So, these are four values with which we can start and we can start traversing one set of all boundaries. Now first of all we will travel to our top boundary. For top boundary, we can say that we can run a for loop which will start from j is equal to 0 or if we have to generalize this then can we say what is 0? This is our starting column, means from whichever starting column to whichever ending column we have to go our loop will run till there for top boundary. So instead of j is equal to 0, we can go from our starting column to our ending column. and every time we can access our matrix of starting row I hope we understood the logic of top boundary because our majority code is going to work on the same logic. That means if I have the value of my starting column and ending column, then can we say that the loop of our top boundary will run from starting column to ending column in which our starting row will be fixed. So starting row is fixed and we will take the value of j from starting column to ending column. This is once we have printed our top boundary. If we want to print our right boundary with this pattern, then we will have to take the So let us write right here. For right boundary, we know that this cell is already covered in top boundary. So can we say that we have to go from this row to our last row. And what is this row? This is starting row plus 1. So from starting row plus 1, we will go to ending row. And every time our ending column will be fixed for this right boundary. So we can run a loop that starts from i is equal to starting row plus 1 to ending row. and every time we can access, print or store our row comma ending column so this way our right boundary will be printed similarly if we talk about bottom boundary then this cell will already be covered so we have to go from here to here what is this place? this is ending column minus 1 and this is the starting column and every time our ending row fix is here so if we for our bottom boundary values to be printed, then our loop will run, j is equal to, this is ending column minus 1, so here from our ending column minus 1, we will run loop till our starting column, and every time we will access matrix of, because this is our last row, so ending row and j value, so in this way we can print one set of our bottom boundary, and similarly if we want to print our left boundary, then in left boundary this value is not there, This value is also not there because we have already printed these two in top and bottom boundaries. So basically we have to go from here to here. What is this value? This is ending row minus 1 and what is this value? This is starting row plus 1. Let us minimize this. So to print our left boundary, basically our loop will run i is equal to our ending row minus 1 to our starting row plus 1. And every time, In this matrix, our row will change but which column will remain the same? Our starting column will remain the same. So we can write the value of starting column in this way. So in this way, we will print a set of top, a set of right, a set of bottom and a set of left boundary. So for them, we have printed the values. Now let's suppose we want to shift our boundaries. We have printed a set of boundaries but for next time, we want this to be our top boundary. This to be our right boundary. This will be our bottom boundary and this will be our left boundary. So for the next bar, we have to change exactly what? For the next bar, basically, our starting row which was printing this top boundary, this time starting row will print this top boundary. So what we can say is that we simply have to do our starting row plus plus so that we can shift towards the next boundary. So we have to do our starting row plus plus. Along with that, can we also say that we have already printed the bottom boundary, i.e. the ending row. To bring the bottom boundary one level up, we have to minus the ending row. Similarly, we do ending row minus minus. Now if we talk about columns, then the right boundary has been printed in the column. So now we don't have to traverse the last column, the ending column. We have to minus the ending column so that the right boundary comes here. and if left boundary was here in the first time, then for the next time if left boundary is here, then for that we have to do plus plus to the starting column also. So basically, as starting row was plus plus, so starting column will also be plus plus. And as ending row was minus minus, so we will be doing minus minus to the ending column also. And by performing these four operations, we will bring the boundary here for the next time. And because we have not kept any fixed value in the code to print all four boundaries. It doesn't mean that we have kept 0 in the starting row or M-1 or N-1. This code is a generic code which depends on these four variables only. Which means that if we are printing a set of boundaries with the help of these four loops, then when we change our boundaries for the next time, then we don't have to change anything in our code as such. With the help of this same code, these four next boundaries are also going to be printed. So these are the four loops which we have to perform again and again. so that we can cover our 2D array in spiral format. Now we are going to solve this question in 3 steps. The first step was to logically understand our boundaries. How can we decide for any spiral matrix, if we have decided to print one set of boundaries, how can we print that set of boundaries? So we have already covered the overall logic for that. The second step for us is to decide what condition we are going to write in our while loop. We know that this... top right bottom and left boundary is the code to print and this code should be repeated again and again but there will be a point when we cover the whole matrix so for that what should be the condition of our while loop we will decide that in the second step and third step will be to solve the problem in which we will discuss a special corner case for this specific problem so now we have only covered the first step of the problem in which we are learning to print our boundaries so once for this much pseudo code let's write our code In the code, we have already opened this question number 54. So here we take our four variables. One will be starting row, which we will start with zero. Before that, let's take the values of m and n. m is the total number of rows, so let's take matrix.size and let us change it to matrix. And let's take an integer n, from which we will take the size of our columns. Starting row will be 0, starting column will also start with 0. Ending row will be equal to m-1 and ending column will be equal to n-1. We have to run a loop, a while loop, till when? Now we are going to discuss the condition in the while loop. But in the while loop, we have to print our 4 boundaries again and again. First top, then right, then bottom and then our left boundary. To print the top boundary, we know that our loop is from starting column to J less than equal to my ending column. We will make J plus plus. Every time in this question, we have to return the spiral order. means instead of printing the order, we are going to return it in the form of a vector so for that let's create a vector also called answer which we are not initializing with any value so simply inside our answer we can push back our value which is matrix of starting row, j so in this way our top boundary loop came then our right boundary loop will come inside the right boundary loop we will start the value of i from starting row plus 1 till i is less than equal to ending row. We have already discussed all these conditions. Matrix of i comma, our ending column will remain the same. Then for our bottom boundary, we will start from ending column minus 1 till our j is greater than equal to our starting column. We will do j minus minus every time. Here our ending row will come and we will have our j. With this, for our left boundary, we will start i equals our ending row from minus 1 till i is greater than or equal to our starting row plus 1. Every time we will do i minus minus because we don't want to cover the values of these two, this starting row and this ending row. We don't want to cover the values of both because it is covered in the top boundary and it is covered in the bottom. So we are starting from here and we are ending here. So every time we are going to print i along with i. our starting column. So in this way we have printed all the four boundaries and after printing all four we will do plus plus for the starting row, we will do minus minus for the ending row, we will do plus plus for the starting column and we will do minus minus for the ending column. So this is what the entire code looks like and as and when we will have values pushed back in the answer, we will return our answer value at the end of the code. Now we have to figure out the major work for us that okay we have to traverse these boundaries in this order. but till when will we traverse? What will be the while condition? For the while condition, let's think logically once what exactly is happening in our code. We are starting the value of starting row from here. Ending row is here. Every time as the loop ends, we do plus plus to our starting row. After doing plus plus, next time our starting row will come here. We will do minus minus to our ending row, it will come here. In a similar way, we will print our next boundaries again. Now in the next time when our starting row will come here and our ending row will become bigger than our starting row. In that case, we will start overlapping our elements. Means starting row already printed these rows. Ending row already printed these rows. So next time when starting row will come here. So this 9 has already been printed as ending row. So can we say that as soon as our starting row value becomes greater than our ending row. In that case, our duplicate elements start printing and we don't want duplicate elements. We don't want to print duplicate boundary. So, can we say that in our code we have to write some kind of condition that our starting row should never be greater than our ending row. Similar case will be for our starting column that our starting column should never be greater than our ending column. Otherwise, again we will get duplicate values. How will it come? We are starting our starting column from here and we are starting our ending column from here. Next, starting column for left boundary will be here and ending column for right boundary will be here. So all these values are printed. Next time when we increase starting column, value will be here and ending column will be here. Now our duplicate values will start to come. So starting column should never be bigger than ending column otherwise values will be printed in duplicate. Now to control this, if we take example of row in our code, we can write condition that our loop should run till our starting row is less than ending row or we can write till our starting row is less than or equal to ending row. These are the two conditions that prevent this. Now the next big question is that which condition should we write logically from both? Now if we take an example of this type of matrix, in which the total number of rows is m, the value is an even number. In that case, any condition written from both of them will work perfectly. But the problem arises in an odd rows or odd columns matrix. For example, if we take this matrix, in which we have odd number of rows and odd number of columns. Let's suppose we have 1, 2, 3, 4, 5, 6, 7, 8 and 9 values. We have started our starting row value from here and this is my ending row. If we keep only this condition, then our top boundary and bottom boundary values will be printed. But in the next iteration, when our starting row will come here and ending row will come here. So in that case, if our starting row and ending row are same, then in that case, the code will not work. If the code does not work in this condition, then our middle elements will not be printed in the boundary. Which will violate the spiral order. And that is why whenever we write our while condition, we will definitely write equal to Because equal to does not matter for even size But for odd size, for example here m is equal to 3 So for all odd matrices, equal to is necessary Because without equal to, the middle elements in the matrix will never be printable We showed the example of row, same thing applies on our column Whenever we write column, we will write less than equal to ending column Because if we see here also, this is my starting column, this is my ending column. If we increase this and bring it here, increase this and bring it here, then both will be pointing the same number of elements. And to print these common elements, we have to write the condition equal to. That is why in our while loop, we want to write, starting row is less than equal to ending row and our starting column is less than equal to our ending column. Now here we have written the conditions with logical AND. Let's understand the major reason behind this with an example. Let's suppose we have a matrix which is 3 x 5 matrix. 3 is m, 5 is n. So we have 3 rows and 5 columns. Now when we run the first time loop, these boundaries will be printed. When we run the second time loop, these boundaries will be printed. So by running the loop only twice, all the boundaries will be printed. Now this condition of running the loop twice is always a small value. means if the value of our row is small then 3 is going to control this condition so whatever the small value is, means if starting row is equal to ending row either we have to exit from the loop or if starting column is equal to ending column then we have to exit from the loop it's not like that, the big value of both will control controlling factor will always control the small value of both because if we have covered all three in terms of row by iterating twice then we will definitely cover in terms of columns So that's why we've used a logical and here. Now let's discuss the third part of our problem which is basically a corner case. And this corner case will generally come in our odd sized matrix cases. For example, we have taken the example of odd sized matrix. If we talk about starting row and ending row. So this is my starting row and this is my ending row. Once we iterate for starting row and ending row, then this will cover our top boundary and this will cover our bottom boundary. Next return ke liye kya hoga, odd size ke anda starting row and ending row dono ek dosre ke equal ho jayenge. Aur jab bhi dono ek dosre ke equal hongi, hume dhaan se dekhna hai, both of them are pointing to the same number of elements. Yani yaha par agar humare paas 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 and 15 hai. Thik hai starting row ending row yaha par aagya. In the beginning, the starting column was here, the ending column was here, but the starting column came here after updating and the ending column came here after updating. So, what can we say, from where our top boundary is? Our top boundary is from starting column to ending column and it is on the starting row. So, what is this 7, 8, 9? It is our top boundary. If we talk about the bottom boundary, then our bottom boundary is on the ending row. So, bottom boundary is also the same number of elements. So here the thing to notice is that whenever the value of our starting row is equal to the value of our ending row, in that case our top boundary is equal to my bottom boundary. That means if the top boundary prints the elements once, then the bottom boundary is going to print the same elements twice. Because of which our elements will repeat. In fact, if we run this problem now, then we are going to get a wrong solution in one of the test cases. and in this test case, since we have 3 rows, the case of odd rows has come, so here our 6 this element is repeating even though 6 has already come under a boundary. So to prevent this, what we do is, if we have already printed the top boundary and we have come to the bottom boundary, then here we first put a check that if our starting row is equal to our ending row, then in that case we do not have to print the bottom boundary again and that is why we want to break out of this bottom boundary. Same thing we do for column in case column number is odd. If any element has already come in right boundary, then to stop its repetition in left, we check if the starting column is equal to my ending column. In that case, we want to break out of the loop so that our right boundary does not overlap with our left boundary and we do not have duplicate elements. So this is a special corner case which we have to consider for odd size matrices. Let's run this once. And now our code is running successfully. So if we sum up our code once, so basically we started with four variables which work to track our boundaries. Starting row, ending row, starting column, ending column. After that we have taken a vector answer in which we are going to store our entire sequence. We are repeatedly printing our top, right, bottom and left boundary. After printing all four, we are updating all our four variables so that we can move to the next boundary. Our conditions will work till our starting row is less than or equal to ending row and till our starting column is less than or equal to ending column. Because in odd row cases, top boundary intersects with bottom and right boundary intersects with left. So, for bottom and left, we have taken a special case. Whenever our starting row value is equal to ending row and whenever our starting column value is equal to ending column. In that case, we will print only one boundary and not bring duplicate elements. and lastly we are simply returning our answer let's submit this code once so we have successfully submitted it this way if we talk about time complexity then it is equal to m into n why? because we are going to every single cell only once when we are traversing the boundaries in our matrix then logically we are traveling the matrix in the same format due to which in every cell we are going at most only once due to which the time complexity is equal to total number of cells which is equal to rows into columns of the matrix. So, in this way, we solve our question of spiral order or spiral matrix. This question can be asked in different forms. Now, we are storing our answer in this vector answer in the submitted question. One more different variation can be this, in which we are just required to print this particular order. So, we can get questions in different variations. So, I hope that you have understood the logic of our question today. I hope you have understood the logic of our question today. As a beginner, if we are studying matrices for the first time, then it is going to be difficult to solve this type of question by ourselves. So if any student is thinking that we have covered so many concepts in this question, how will we think about them by ourselves? So that is the thing that we will be coming with practice. Do not expect that we are studying the topic of 2D arrays for the first time and the logic of this question will hit us for the first time or we will be able to write the solution by ourselves. Definitely, if you are a beginner, you are going to require some help. In this way, we will solve many questions and then our logic will start building. So I hope by solving this question, we have learnt something new. I have tried my best to cover every corner case, every condition. In fact, why are we using logical and between two small things? Why didn't we use or use any other condition? I have tried to cover all these things in the lecture. So that logically we don't feel that we are remembering things. There is a logical reason behind everything. Why do we get less than condition? Why do we get less than equal to condition? And when we start understanding these things in the question, then our logic gets strengthened in the long term. So if you have successfully completed the lecture, you can mark your attendance down in the comments. Along with this, you can also share your progress with me on Twitter, whose link you will find in the description box below. And also you can tell me in the comments, that from today's lecture, which new thing we have in programming, in DSA, which we have learned. That's all for today. See you in the next lecture. Till then, keep learning and keep exploring.

This problem is also problem number 54 available on Leetcode. We have a matrix given in this way whose size is m cross nk equal. For example, here our m value is 4 and our n value is 4. So, here rows are also equal to 4 and columns are also equal to 4. We have to travel this given matrix in a spiral way and store all its elements.

Traveling in a spiral way means that first of all we will cover our top boundary from left to right. So, we will have elements 1, 2, 3, 4. Then we will cover our right boundary from top to bottom. So, we will have elements 8, 12 and 16. means as we go on each cell, we are storing its output in spirally. After that we will cover our bottom boundary, in which we will get elements 15, 14 and 13. And then we will cover our left boundary, in which we will get elements 9 and 5. So whenever we are traveling in spiral form, we don't have to repeat any cell.

Now let's suppose we have covered our outer boundary, now we will cover the inner boundary inside. So again we will follow the same format that first we have to write the top boundary, then we have to cover the right boundary, then we have to cover the bottom boundary and then we have to cover the left boundary. So first of all we will have the top which will be 6 and 7, then we will have the right which will be 11, then the bottom which will be 10 and then when we go to the top, since we have already covered 6 here, we do not have to repeat it. So in a way this is our output which should be produced for this particular 2D array or a matrix. So we have to cover our given 2D area in spiral way in these formats till the time all the elements of our matrix are not exhausted.

Till the time we don't travel on every cell of our matrix. Now we already know that we have to cover the boundaries of our matrix. So for boundaries, first we have to go to the top boundary, then to the right, then to the bottom, then to the left.

Now whenever we talk about boundaries, we should always know from where any boundary goes to where. For example, if we talk about the first layer of boundaries, then this will be our top boundary in which we are going from the 0th column to the n-1th column and in which our row is number 0. If we talk about the right boundary, then here our boundary exists from 0 to m-1 in which our column number is fixed which is n-1. If we talk about the bottom boundary, then it is going from n-1 to 0 and in which our row is fixed which is m-1.

And if we talk about the left boundary, then it will go from m-1 to 0, in which our column is fixed, which is equal to 0. So whenever we talk about any boundary, either a row is fixed or a column is fixed. For example, our row number is fixed in the top boundary, our row number is fixed in the bottom boundary. If we talk about column-wise left and right boundaries, then our column number is fixed in them.

So can we say that we can take 4 variables to track this information? Whenever we talk about boundary, we should have row and column information. So to track this information, we can make use of four variables through which we can track different rows and columns.

We are talking about our outer boundary, not the pattern logic. We are thinking in this direction, if we had to print top right bottom left, how would we print them? We could take variables for them, one would be our starting row variable, another would be our ending row variable. Similarly, one could be our variable starting column and one could be ending column.

We know that in terms of our boundaries, our starting row will be 0 where our top boundary starts. So, starting row will also be 0 and starting column will also be 0. Ending row, i.e. where the bottom boundary is, that is equal to m-1 and ending column is equal to n-1. So, these are four values with which we can start and we can start traversing one set of all boundaries.

Now first of all we will travel to our top boundary. For top boundary, we can say that we can run a for loop which will start from j is equal to 0 or if we have to generalize this then can we say what is 0? This is our starting column, means from whichever starting column to whichever ending column we have to go our loop will run till there for top boundary. So instead of j is equal to 0, we can go from our starting column to our ending column. and every time we can access our matrix of starting row I hope we understood the logic of top boundary because our majority code is going to work on the same logic.

That means if I have the value of my starting column and ending column, then can we say that the loop of our top boundary will run from starting column to ending column in which our starting row will be fixed. So starting row is fixed and we will take the value of j from starting column to ending column. This is once we have printed our top boundary.

If we want to print our right boundary with this pattern, then we will have to take the So let us write right here. For right boundary, we know that this cell is already covered in top boundary. So can we say that we have to go from this row to our last row. And what is this row?

This is starting row plus 1. So from starting row plus 1, we will go to ending row. And every time our ending column will be fixed for this right boundary. So we can run a loop that starts from i is equal to starting row plus 1 to ending row. and every time we can access, print or store our row comma ending column so this way our right boundary will be printed similarly if we talk about bottom boundary then this cell will already be covered so we have to go from here to here what is this place? this is ending column minus 1 and this is the starting column and every time our ending row fix is here so if we for our bottom boundary values to be printed, then our loop will run, j is equal to, this is ending column minus 1, so here from our ending column minus 1, we will run loop till our starting column, and every time we will access matrix of, because this is our last row, so ending row and j value, so in this way we can print one set of our bottom boundary, and similarly if we want to print our left boundary, then in left boundary this value is not there, This value is also not there because we have already printed these two in top and bottom boundaries.

So basically we have to go from here to here. What is this value? This is ending row minus 1 and what is this value?

This is starting row plus 1. Let us minimize this. So to print our left boundary, basically our loop will run i is equal to our ending row minus 1 to our starting row plus 1. And every time, In this matrix, our row will change but which column will remain the same? Our starting column will remain the same. So we can write the value of starting column in this way. So in this way, we will print a set of top, a set of right, a set of bottom and a set of left boundary.

So for them, we have printed the values. Now let's suppose we want to shift our boundaries. We have printed a set of boundaries but for next time, we want this to be our top boundary. This to be our right boundary.

This will be our bottom boundary and this will be our left boundary. So for the next bar, we have to change exactly what? For the next bar, basically, our starting row which was printing this top boundary, this time starting row will print this top boundary.

So what we can say is that we simply have to do our starting row plus plus so that we can shift towards the next boundary. So we have to do our starting row plus plus. Along with that, can we also say that we have already printed the bottom boundary, i.e. the ending row.

To bring the bottom boundary one level up, we have to minus the ending row. Similarly, we do ending row minus minus. Now if we talk about columns, then the right boundary has been printed in the column. So now we don't have to traverse the last column, the ending column.

We have to minus the ending column so that the right boundary comes here. and if left boundary was here in the first time, then for the next time if left boundary is here, then for that we have to do plus plus to the starting column also. So basically, as starting row was plus plus, so starting column will also be plus plus. And as ending row was minus minus, so we will be doing minus minus to the ending column also.

And by performing these four operations, we will bring the boundary here for the next time. And because we have not kept any fixed value in the code to print all four boundaries. It doesn't mean that we have kept 0 in the starting row or M-1 or N-1. This code is a generic code which depends on these four variables only.

Which means that if we are printing a set of boundaries with the help of these four loops, then when we change our boundaries for the next time, then we don't have to change anything in our code as such. With the help of this same code, these four next boundaries are also going to be printed. So these are the four loops which we have to perform again and again.

so that we can cover our 2D array in spiral format. Now we are going to solve this question in 3 steps. The first step was to logically understand our boundaries. How can we decide for any spiral matrix, if we have decided to print one set of boundaries, how can we print that set of boundaries? So we have already covered the overall logic for that.

The second step for us is to decide what condition we are going to write in our while loop. We know that this... top right bottom and left boundary is the code to print and this code should be repeated again and again but there will be a point when we cover the whole matrix so for that what should be the condition of our while loop we will decide that in the second step and third step will be to solve the problem in which we will discuss a special corner case for this specific problem so now we have only covered the first step of the problem in which we are learning to print our boundaries so once for this much pseudo code let's write our code In the code, we have already opened this question number 54. So here we take our four variables.

One will be starting row, which we will start with zero. Before that, let's take the values of m and n. m is the total number of rows, so let's take matrix.size and let us change it to matrix.

And let's take an integer n, from which we will take the size of our columns. Starting row will be 0, starting column will also start with 0. Ending row will be equal to m-1 and ending column will be equal to n-1. We have to run a loop, a while loop, till when?

Now we are going to discuss the condition in the while loop. But in the while loop, we have to print our 4 boundaries again and again. First top, then right, then bottom and then our left boundary. To print the top boundary, we know that our loop is from starting column to J less than equal to my ending column.

We will make J plus plus. Every time in this question, we have to return the spiral order. means instead of printing the order, we are going to return it in the form of a vector so for that let's create a vector also called answer which we are not initializing with any value so simply inside our answer we can push back our value which is matrix of starting row, j so in this way our top boundary loop came then our right boundary loop will come inside the right boundary loop we will start the value of i from starting row plus 1 till i is less than equal to ending row. We have already discussed all these conditions. Matrix of i comma, our ending column will remain the same.

Then for our bottom boundary, we will start from ending column minus 1 till our j is greater than equal to our starting column. We will do j minus minus every time. Here our ending row will come and we will have our j.

With this, for our left boundary, we will start i equals our ending row from minus 1 till i is greater than or equal to our starting row plus 1. Every time we will do i minus minus because we don't want to cover the values of these two, this starting row and this ending row. We don't want to cover the values of both because it is covered in the top boundary and it is covered in the bottom. So we are starting from here and we are ending here.

So every time we are going to print i along with i. our starting column. So in this way we have printed all the four boundaries and after printing all four we will do plus plus for the starting row, we will do minus minus for the ending row, we will do plus plus for the starting column and we will do minus minus for the ending column. So this is what the entire code looks like and as and when we will have values pushed back in the answer, we will return our answer value at the end of the code. Now we have to figure out the major work for us that okay we have to traverse these boundaries in this order.

but till when will we traverse? What will be the while condition? For the while condition, let's think logically once what exactly is happening in our code. We are starting the value of starting row from here.

Ending row is here. Every time as the loop ends, we do plus plus to our starting row. After doing plus plus, next time our starting row will come here.

We will do minus minus to our ending row, it will come here. In a similar way, we will print our next boundaries again. Now in the next time when our starting row will come here and our ending row will become bigger than our starting row.

In that case, we will start overlapping our elements. Means starting row already printed these rows. Ending row already printed these rows.

So next time when starting row will come here. So this 9 has already been printed as ending row. So can we say that as soon as our starting row value becomes greater than our ending row. In that case, our duplicate elements start printing and we don't want duplicate elements.

We don't want to print duplicate boundary. So, can we say that in our code we have to write some kind of condition that our starting row should never be greater than our ending row. Similar case will be for our starting column that our starting column should never be greater than our ending column. Otherwise, again we will get duplicate values. How will it come?

We are starting our starting column from here and we are starting our ending column from here. Next, starting column for left boundary will be here and ending column for right boundary will be here. So all these values are printed. Next time when we increase starting column, value will be here and ending column will be here.

Now our duplicate values will start to come. So starting column should never be bigger than ending column otherwise values will be printed in duplicate. Now to control this, if we take example of row in our code, we can write condition that our loop should run till our starting row is less than ending row or we can write till our starting row is less than or equal to ending row.

These are the two conditions that prevent this. Now the next big question is that which condition should we write logically from both? Now if we take an example of this type of matrix, in which the total number of rows is m, the value is an even number.

In that case, any condition written from both of them will work perfectly. But the problem arises in an odd rows or odd columns matrix. For example, if we take this matrix, in which we have odd number of rows and odd number of columns. Let's suppose we have 1, 2, 3, 4, 5, 6, 7, 8 and 9 values. We have started our starting row value from here and this is my ending row.

If we keep only this condition, then our top boundary and bottom boundary values will be printed. But in the next iteration, when our starting row will come here and ending row will come here. So in that case, if our starting row and ending row are same, then in that case, the code will not work.

If the code does not work in this condition, then our middle elements will not be printed in the boundary. Which will violate the spiral order. And that is why whenever we write our while condition, we will definitely write equal to Because equal to does not matter for even size But for odd size, for example here m is equal to 3 So for all odd matrices, equal to is necessary Because without equal to, the middle elements in the matrix will never be printable We showed the example of row, same thing applies on our column Whenever we write column, we will write less than equal to ending column Because if we see here also, this is my starting column, this is my ending column.

If we increase this and bring it here, increase this and bring it here, then both will be pointing the same number of elements. And to print these common elements, we have to write the condition equal to. That is why in our while loop, we want to write, starting row is less than equal to ending row and our starting column is less than equal to our ending column. Now here we have written the conditions with logical AND. Let's understand the major reason behind this with an example.

Let's suppose we have a matrix which is 3 x 5 matrix. 3 is m, 5 is n. So we have 3 rows and 5 columns. Now when we run the first time loop, these boundaries will be printed.

When we run the second time loop, these boundaries will be printed. So by running the loop only twice, all the boundaries will be printed. Now this condition of running the loop twice is always a small value. means if the value of our row is small then 3 is going to control this condition so whatever the small value is, means if starting row is equal to ending row either we have to exit from the loop or if starting column is equal to ending column then we have to exit from the loop it's not like that, the big value of both will control controlling factor will always control the small value of both because if we have covered all three in terms of row by iterating twice then we will definitely cover in terms of columns So that's why we've used a logical and here.

Now let's discuss the third part of our problem which is basically a corner case. And this corner case will generally come in our odd sized matrix cases. For example, we have taken the example of odd sized matrix.

If we talk about starting row and ending row. So this is my starting row and this is my ending row. Once we iterate for starting row and ending row, then this will cover our top boundary and this will cover our bottom boundary.

Next return ke liye kya hoga, odd size ke anda starting row and ending row dono ek dosre ke equal ho jayenge. Aur jab bhi dono ek dosre ke equal hongi, hume dhaan se dekhna hai, both of them are pointing to the same number of elements. Yani yaha par agar humare paas 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 and 15 hai. Thik hai starting row ending row yaha par aagya. In the beginning, the starting column was here, the ending column was here, but the starting column came here after updating and the ending column came here after updating.

So, what can we say, from where our top boundary is? Our top boundary is from starting column to ending column and it is on the starting row. So, what is this 7, 8, 9?

It is our top boundary. If we talk about the bottom boundary, then our bottom boundary is on the ending row. So, bottom boundary is also the same number of elements.

So here the thing to notice is that whenever the value of our starting row is equal to the value of our ending row, in that case our top boundary is equal to my bottom boundary. That means if the top boundary prints the elements once, then the bottom boundary is going to print the same elements twice. Because of which our elements will repeat.

In fact, if we run this problem now, then we are going to get a wrong solution in one of the test cases. and in this test case, since we have 3 rows, the case of odd rows has come, so here our 6 this element is repeating even though 6 has already come under a boundary. So to prevent this, what we do is, if we have already printed the top boundary and we have come to the bottom boundary, then here we first put a check that if our starting row is equal to our ending row, then in that case we do not have to print the bottom boundary again and that is why we want to break out of this bottom boundary.

Same thing we do for column in case column number is odd. If any element has already come in right boundary, then to stop its repetition in left, we check if the starting column is equal to my ending column. In that case, we want to break out of the loop so that our right boundary does not overlap with our left boundary and we do not have duplicate elements.

So this is a special corner case which we have to consider for odd size matrices. Let's run this once. And now our code is running successfully.

So if we sum up our code once, so basically we started with four variables which work to track our boundaries. Starting row, ending row, starting column, ending column. After that we have taken a vector answer in which we are going to store our entire sequence.

We are repeatedly printing our top, right, bottom and left boundary. After printing all four, we are updating all our four variables so that we can move to the next boundary. Our conditions will work till our starting row is less than or equal to ending row and till our starting column is less than or equal to ending column.

Because in odd row cases, top boundary intersects with bottom and right boundary intersects with left. So, for bottom and left, we have taken a special case. Whenever our starting row value is equal to ending row and whenever our starting column value is equal to ending column. In that case, we will print only one boundary and not bring duplicate elements.

and lastly we are simply returning our answer let's submit this code once so we have successfully submitted it this way if we talk about time complexity then it is equal to m into n why? because we are going to every single cell only once when we are traversing the boundaries in our matrix then logically we are traveling the matrix in the same format due to which in every cell we are going at most only once due to which the time complexity is equal to total number of cells which is equal to rows into columns of the matrix. So, in this way, we solve our question of spiral order or spiral matrix.

This question can be asked in different forms. Now, we are storing our answer in this vector answer in the submitted question. One more different variation can be this, in which we are just required to print this particular order.

So, we can get questions in different variations. So, I hope that you have understood the logic of our question today. I hope you have understood the logic of our question today. As a beginner, if we are studying matrices for the first time, then it is going to be difficult to solve this type of question by ourselves. So if any student is thinking that we have covered so many concepts in this question, how will we think about them by ourselves?

So that is the thing that we will be coming with practice. Do not expect that we are studying the topic of 2D arrays for the first time and the logic of this question will hit us for the first time or we will be able to write the solution by ourselves. Definitely, if you are a beginner, you are going to require some help.

In this way, we will solve many questions and then our logic will start building. So I hope by solving this question, we have learnt something new. I have tried my best to cover every corner case, every condition. In fact, why are we using logical and between two small things?

Why didn't we use or use any other condition? I have tried to cover all these things in the lecture. So that logically we don't feel that we are remembering things. There is a logical reason behind everything.

Why do we get less than condition? Why do we get less than equal to condition? And when we start understanding these things in the question, then our logic gets strengthened in the long term. So if you have successfully completed the lecture, you can mark your attendance down in the comments.

Along with this, you can also share your progress with me on Twitter, whose link you will find in the description box below. And also you can tell me in the comments, that from today's lecture, which new thing we have in programming, in DSA, which we have learned. That's all for today. See you in the next lecture. Till then, keep learning and keep exploring.

Transcript for:Understanding Spiral Matrix Traversal

Transcript for:
Understanding Spiral Matrix Traversal