Rotate Elements in Matrix – Interview Question

Rotate Elements in Matrix – Interview Question

September 26, 2018 Uncategorized 0


Rotate Elements in a Matrix.

Let’s find out how to answer this question in a technical interview.

Let’s take a sample matrix

1     2      3      4

5     6      7      8

9     10    11    12

13   14    15    16

 

If we rotate it, this is how it will look like

5      1      2      3

9     10     6     4

13   11    7      8

14   15    16    12

In order to write this program, let’s see how we did it. We first rotated the outermost ring, one element each in clockwise direction. Next, we rotated the second ring, again one element each in the clock wise direction. So we need to think in terms of one ring at a time.

 

So if we were to do it for only one ring, our pseudo code will be something like this:

 

  1. Read element at matrix[1][0]. Let’s call it previous.
  2. Loop through first row. Put previous in the beginning of the row. Move elements to the right. Keep the last element of first row in previous.
  3. Loop through last column. Leaving the first row. Put previous as the first element. Move other elements to the bottom. Keep the last element of last column in previous.
  4. Loop through last row right to left, leaving the last column. Put previous as the first element. Move all elements tot the left. Keep the first element of last row in previous.
  5. Loop through first column bottom up. Put previous as first element. Move all elements up except the topmost element which was covered earlier.

 

Now if we want to loop through one ring at a time, we simply put an outer loop starting from layer 0 to layer n/2.

 

The above will work only for a square matrix. If it were a rectangular matrix, we can’t do 0 to n/2. For e.g.

1      4

5      8

9     12

13   16

 

will be:

5       1

9       4

13     8

16   12

We will have to do a while loop. With each ring we can keep incrementing the row and column number where we are at. And we will have to keep decrementing the maxrow and maxColumn count once we finish a ring. If the row is less than maxrow and col is less than max column, then we continue.

 

Void RotateMatrix(int[][] matrix, int RowsNum, int ColsNum){

Row = 0

Col = 0

MaxRow = RowsNum – 1

MaxCol = ColsNum – 1

While(row < MaxRow && col < MaxCol){

If(row+1 == MaxRow || col+1 == MaxCol)

break;

Int previous = matrix[row+1][col]

//TOP ROW

For(int i = col; i <= Maxcol; i++){

Int current = mat[row][i];

Mat[row][i] = previous;

previous = current;

}

Row++;

//RIGHT COLUMN

For(int j = row; j <= maxRow; j++){

Int current = matrix[j][maxCol];

matrix[j][maxCol] = previous;

previous = current;

}

maxCol–;

//BOTTOM ROW

if(row<maxRow + 1){

For(int i = maxCol; i >= col; i–){

Int current = mat[maxRow][i];

Mat[maxRow][i] = previous;

previous = current;

}

maxRow–;

}

//LEFT COLUMN

If(col < maxCol + 1){

For(int i = maxRol; i >= row; i–){

Int current = mat[i][col];

Mat[i][col] = previous;

previous = current;

}

Col++;

}

}

}

I have the actual running C# code on Github here.

Please make sure to test run it after writing the code and take care of edge conditions. If you have followed these steps then I would say you have successfully answered the interview question.

For more such questions, please subscribe to coach4dev. Until next time, Happy Coding!!!