The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Integer Division

When a dividend integer divides a divisor integer, the quotient (answer) is a whole number and a remainder. The remainder may be zero. Integer division is the division where the remainder is abandoned and not used.

For example, in integer division, 9 / 2 is 4 and not 8½; 8 / 2 is still 4 in integer division. Also, in integer division, 4 / 2 is 2; 3 / 2 is 1; 2 / 2 is 1; and 1 / 2 is 0.

Problem

Given a rectangular matrix, the task is to rotate its elements clockwise by one step.

In the following examples, p is the number of rows and q is the number of columns.

Example 1: 
Input:  mat[][] = [[1   2   3   4   5]
                   [12  13  14  15  6]
                   [11  10  9   8   7]]
                   
Output: 
                  [[12  1   2   3   4]
                   [11  13  14  15  5]
                   [10  9   8   7   6]]

The number of columns, q is greater than the number of rows, p. The number of rows is three, and odd. The elements 13, 14, and 15 in the middle row, cannot change their positions, after rotation. The first element in the middle row changes its position; the last element in the middle row changes its position; 1, 1 on either ends.

Example 2: 
Input:  mat[][] = [[1    2    3    4    5    6]
                   [16   17   18   19   20   7]
                   [15   24   23   22   21   8]
                   [14   13   12   11   10   9]]
                   
Output: 
                  [[16  1   2   3   4   5]
                   [15  24  17  18  19  6]
                   [14  23  22  21  20  7]
                   [13  12  11  10  9   8]]

The number of columns, q is greater than the number of rows, p. The number of rows is four, and even. Every element in the 2D array is shifted, because the number of lines from the shorter side of the matrix is even.

Example 3: 
Input:  mat[][] = [[1    2    3    4    5     6    7    8]
                   [22   23   24   25   26    27   28   9]
                   [21   36   37   38   39    40   29   10]
                   [20   35   34   33   32    31   30   11]
                   [19   18   17   16   15    14   13   12]]
                   
Output: 
                   [[22  1   2   3   4    5    6    7]
                    [21  36  23  24  25   26   27   8]
                    [20  35  37  38  39   40   28   9]
                    [19  35  33  32  31   30   29   10]
                    [18  17  16  15  14   13   12   11]]

The number of columns, q is greater than the number of rows, p. The number of rows is five, and odd. The elements: 37, 38, 39, and 40 in the middle row cannot change their positions, after rotation. The first two elements in the middle row change their positions; the last two elements in the middle row change their positions; 2, 2 on either ends.

Example 4: 
Input:  mat[][] = [[1    2    3]
                   [12   13   4]
                   [11   14   5]
                   [10   15   6]
                   [9    8    7]]
                   
Output: 
                   [[12   1    2]
                    [11   13   3]
                    [10   14   4]
                    [9    15   5]
                    [8    7    6]]

The number of rows, p is greater than the number of columns, q. The number of columns is three, and odd. The elements: 13, 14, and 15 in the center column cannot change their positions, after rotation. The first element in the center column changes its position; the last element in the center column changes its position; 1, 1 on either ends.

Example 5: 
Input:  mat[][] = [[1    2    3    4]
                   [16   17   18   5]
                   [15   24   19   6]
                   [14   23   20   7]
                   [13   22   21   8]
                   [12   11   10   9]]
                   
Output: 
                  [[16   1    2    3]
                   [15   24   17   4]
                   [14   23   18   5]
                   [13   22   19   6]
                   [12   21   20   7]
                   [11   10   9    8]]

The number of rows, p is greater than the number of columns, q. The number of columns is four, and even. Every element in the 2D array is shifted, because the number of lines from the shorter side of the matrix is even.

Example 6: 
Input:  mat[][] = [[1   2   3   4   5]
                   [22  23  24  25  6]
                   [21  36  37  26  7]
                   [20  35  38  27  8]
                   [19  34  39  28  9]
                   [18  33  40  29  10]
                   [17  32  31  30  11]
                   [16  15  14  13  12]]
                   
Output: 
                  [[22  1   2   3   4]
                   [21  36  23  24  5]
                   [20  35  37  25  6]
                   [19  34  38  26  7]
                   [18  33  39  27  8]
                   [17  32  40  28  9]
                   [16  31  30  29  10]
                   [15  14  13  12  11]]

The number of rows, p is greater than the number of columns, q. The number of columns is five, and odd. The elements: 37, 38, 39 and 40 in the center column cannot change their positions, after rotation. The first two elements in the center column change their positions; the last two elements in the center column change their positions; 2, 2 on either ends.

Solution in O(n x m) Time

Case When Number of Rows is Smaller than Number of Columns

When the number of rows is smaller than the number of columns, and it is even, all the elements in the matrix are shifted (rotated).

However, when the number of rows is smaller than the number of columns, and it is odd, one or more elements in the middle row cannot be shifted (rotated).

- If the number of rows is 1, that one row is the middle row at row-index zero. This 0 is obtained from the integer division of 1 / 2 = 0. And no element is shifted (rotated) in that middle row. Zero element from either ends of the row is shifted (rotated). 0 here refers to both the row index 0 and the number of elements shifted in the middle row.
- If the number of rows is 3, the middle row is the second row of row-index 1. This 1 is obtained from the integer division of 3 / 2 = 1. And the first and last elements of the middle row are shifted (rotated): 1, 1 on either ends. The rest of the elements in that middle row are not shifted. 1 here refers to both the row index 1 and the number of elements shifted in the middle row.
- If the number of rows is 5, the middle row is the third row of row-index 2. This 2 is obtained from the integer division of 5 / 2 = 2. And the first two elements and last two elements of the middle row are shifted (rotated): 2, 2 on either ends. The rest of the elements in that middle row are not shifted. 2 here refers to both the row index 2 and the number of elements shifted in the middle row.
- If the number of rows is 7, the middle row is the fourth row of row-index 3. This 3 is obtained from the integer division of 7 / 2 = 3. And the first three elements and last three elements of the middle row are shifted (rotated): 3, 3 on either ends. The rest of the elements in that middle row are not shifted. 0 here refers to both the row index 3 and the number of elements shifted in the middle row.
- And so on . . .

Case When Number of Columns is Smaller than Number of Rows

When the number of columns is smaller than the number of rows, and it is even, all the elements in the matrix are shifted (rotated).

However, when the number of columns is smaller than the number of rows, and it is odd, one or more elements in the center column are not shifted (rotated).

- If the number of columns is 1, that one column is the center column at column-index zero. This 0 is obtained from the integer division of 1 / 2 = 0. And no element is shifted (rotated) in that center column. Zero element from either ends of the column is shifted (rotated). 0 here refers to both the column index 0 and the number of elements shifted in the center column.
- If the number of columns is 3, the middle column is the second column of column-index 1. This 1 is obtained from the integer division of 3 / 2 = 1. And the first and last elements of the center column are shifted (rotated): 1, 1 on either ends. The rest of the elements in that center column are not shifted. 1 here refers to both the column index 1 and the number of elements shifted in the center column.
- If the number of columns is 5, the center column is the third column of column-index 2. This 2 is obtained from the integer division of 5 / 2 = 2. And the first two elements and last two elements of the center column are shifted (rotated): 2, 2 on either ends. The rest of the elements in that center column are not shifted. 2 here refers to both the column index 2 and the number of elements shifted in the center column.
- If the number of columns is 7, the center column is the fourth column of column-index 3. This 3 is obtained from the integer division of 7 / 2 = 3. And the first three elements and last three elements of the center column are shifted (rotated): 3, 3 on either ends. The rest of the elements in that center column are not shifted. 3 here refers to both the column index 3 and the number of elements shifted in the center column.
- And so on . . .

Algorithm

Use four non-nesting for-loops, in a while-loop, to move in the four directions: right, down, left, and up, one element at a time for each rectangular ring of elements, starting from the outermost ring (top-left). This simulates the clockwise rotation, by rotating each ring in the matrix.

So, do the outermost ring, then the inner ring, then the ring inwards, and so on, until the innermost ring is done or addressed. If the number of rows in the matrix is smaller than the number of columns, and if the number is odd, then one or more of the elements in the middle row will not change their positions. If the number of columns in the matrix is smaller than the number of rows, and if the number is odd, then one or more of the elements in the center column will not change their positions.

In order to know the number of extreme elements in the middle row, that will change their positions, use integer division, thus: number of rows / 2, and throw away the remainder. To know the middle row index, still use integer division. For the elements that will not change their positions, just copy the elements that will not change their positions, in the middle row, from the given matrix to the destination (output) matrix.

In order to know the number of extreme elements in the center column, that will change their positions, use integer division, thus: number of columns / 2, and throw away the remainder. To know the center column index, still use integer division. For the elements that will not change their positions, just copy the elements that will not change their positions, in the center column, from the given matrix to the destination (output) matrix.

Strategy

There is the input matrix. In the called function, an empty matrix of the same order is declared. For a top row of a ring, the first m-1 elements in the input matrix are copied to the next m-1 positions in the output matrix, in same row, and by that, doing the top row. For the right column of a ring, the first n-1 elements in the input matrix are copied to the next n-1 positions in the output matrix, in same column, and by that, doing the right column. For the bottom row of a ring, the last m-1 elements in the input matrix are copied to the previous m-1 positions in the output matrix, in same row, and by that, doing the bottom row. For the left column of a ring, the last n-1 elements in the input matrix are copied to the previous n-1 positions in the output matrix, in same column, and by that, doing the left column.

The values of n and m are then reduced by 1, and the copying of the inner ring is done. This continuous until the innermost ring is done or addressed.

There are the usual variables, i and j for the coordinates (indexes) of each element.

There is the variable, newleft for the left index of the current ring bottom row and newTop for the top index of the current ring left column.

The right end variable for the current ring top row index is m-1, and the bottom right variable for the current ring right column index is n-1.

In the program below, p is the number of rows in the outermost ring column, and q is the number of columns in the outermost ring row.

The program

The program is (read through the code and comments):

#include <stdio.h>

void rotateMatrix1(int mat[][4], int n, int m) {
    int rotmat[n][m];    //rotated matrix
    int i=0, j=0;
    int p=n, q=m;    //original number of rows and columns
    int newTop = 0;
    int newleft = 0;

    // Rotate the matrix in rectangular rings
    while (n != p/2 && m != q/2) {    //integer division
        // Traverse the top new row from left to right
        for (j = j; j < m-1; j++) {
            if (j+1 != m)
                rotmat[i][j+1] = mat[i][j];    
        }

        // Traverse the last new column from "2nd" row
        for (i=i; i < n-1; i++) {    
            if (i+1 != n)
                rotmat[i+1][j] = mat[i][j];
        }

        // Traverse the bottom new row from "last-but-one" column to "first" column
        if (n > 1) { // Check to avoid duplicating row in single-row matrix
            for (j = m - 1; j > newleft; j--) {
                if (j != newleft)
                    rotmat[i][j-1] = mat[i][j];
            }
        } 
        
        // Traverse the first new column from last-but-one row up to second row
        if (m > 1) { // Check to avoid duplicating column in single-column matrix
            for (i = n - 1; i > newTop; i--) {
                if (i != newTop)
                    rotmat[i-1][j] = mat[i][j];
            }
        } 
        
        //go to inner rectangular ring
        n = n - 1;
        m = m - 1;
        i = i + 1;
        j = j + 1;
        newTop = newTop + 1;    //go one step down
        newleft = newleft + 1;    //go one step right
    }
    
    //Number of rows is odd
    if (p % 2 == 1) {
        //number of extreme elements in middle row on both sides
        int noExtreme = p / 2;    //integer division
        int rowIndex = p / 2;    //integer division
        //copy elements whose positions did not change
        for (int j=noExtreme; j < q-noExtreme; j++)
            rotmat[rowIndex][j] = mat[rowIndex][j];
    }
    
    //Number of columns is odd
    if (q % 2 == 1) {
        //number of extreme elements in middle column (top & bottom)
        int noExtreme = q / 2;    //integer division
        int colIndex = q / 2;    //integer division
        //copy elements whose positions did not change
        for (int i=noExtreme; i < p-noExtreme; i++)
            rotmat[i][colIndex] = mat[i][colIndex];
    }
    
    for (int i=0; i < p; i++) {
        for (int j=0; j < q; j++) {
            printf("%i, ", rotmat[i][j]);
        }
        printf("\n");
    }
}

int main(int argc, char **argv) 
{
/*
    int n=3, m=5;
    int mat[3][5] = {{1,  2,  3,  4,  5},
                     {12, 13, 14, 15, 6},
                     {11, 10, 9,  8,  7}};
      
    rotateMatrix1(mat, n, m);
*/
/*
    int n2=4, m2=6;
    int mat2[4][6] = {{1,  2,  3,  4,  5,  6},
                      {16, 17, 18, 19, 20, 7},
                      {15, 24, 23, 22, 21, 8},
                      {14, 13, 12, 11, 10, 9}};
                    
    rotateMatrix1(mat2, n2, m2);
*/
/*
    int n3=5, m3=8;
    int mat3[5][8] = {{1,  2,  3,  4,  5,  6,  7,  8 },
                      {22, 23, 24, 25, 26, 27, 28, 9 },
                      {21, 36, 37, 38, 39, 40, 29, 10},
                      {20, 35, 34, 33, 32, 31, 30, 11},
                      {19, 18, 17, 16, 15, 14, 13, 12}};
      
    rotateMatrix1(mat3, n3, m3);
*/
/*
    int n4=5, m4=3;
    int mat4[5][3] = {{1,  2,  3},
                      {12, 13, 4},
                      {11, 14, 5},
                      {10, 15, 6},
                      {9,  8,  7}};
      
    rotateMatrix1(mat4, n4, m4);
*/
/*
    int n5=6, m5=4;
    int mat5[6][4] = {{1,  2,  3,  4},
                      {16, 17, 18, 5},
                      {15, 24, 19, 6},
                      {14, 23, 20, 7},
                      {13, 22, 21, 8},
                      {12, 11, 10, 9}};
                    
    rotateMatrix1(mat5, n5, m5);
*/

    int n6=8, m6=5;
    int mat6[8][5] = {{1,  2,  3,  4,  5},
                      {22, 23, 24, 25, 6},
                      {21, 36, 37, 26, 7},
                      {20, 35, 38, 27, 8},
                      {19, 34, 39, 28, 9},
                      {18, 33, 40, 29, 10},
                      {17, 32, 31, 30, 11},
                      {16, 15, 14, 13, 12}};
      
    rotateMatrix1(mat6, n6, m6);

    return 0;
}

Remove the first pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][5]" for the 3-by-5 input matrix. In this case, the output should be:

    12,  1,  2,  3,  4, 
    11,  13, 14, 15, 5, 
    10,  9,  8,  7,  6, 

Put back the first pair of block quote markers (/* and */). Remove the second pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][6]" for the 4-by-6 input matrix. In this case, the output should be:

    16,  1,  2,  3,  4,  5, 
    15,  24, 17, 18, 19, 6, 
    14,  23, 22, 21, 20, 7, 
    13,  12, 11, 10, 9,  8,

Put back the second pair of block quote markers (/* and */). Remove the third pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][8]" for the 5-by-8 input matrix . In this case, the output should be:

    22, 1,  2,  3,  4,  5,  6,  7, 
    21, 36, 23, 24, 25, 26, 27, 8, 
    20, 35, 37, 38, 39, 40, 28, 9, 
    19, 34, 33, 32, 31, 30, 29, 10, 
    18, 17, 16, 15, 14, 13, 12, 11, 

Put back the third pair of block quote markers (/* and */). Remove the fourth pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][3]" for the 5-by-3 input matrix. In this case, the output should be:

    12, 1,  2, 
    11, 13, 3, 
    10, 14, 4, 
    9,  15, 5, 
    8,  7,  6, 

Put back the fourth pair of block quote markers (/* and */). Remove the fifth pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][4]" for the 6-by-4 input matrix. In this case, the output should be:

    16, 1,  2,  3, 
    15, 24, 17, 4, 
    14, 23, 18, 5, 
    13, 22, 19, 6, 
    12, 21, 20, 7, 
    11, 10, 9,  8, 

Put back the fifth pair of block quote markers (/* and */). Remove the sixth pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function "mat[][5]" for the 8-by-5 input matrix . In this case, the output should be:

    22, 1,  2,  3,  4, 
    21, 36, 23, 24, 5, 
    20, 35, 37, 25, 6, 
    19, 34, 38, 26, 7, 
    18, 33, 39, 27, 8, 
    17, 32, 40, 28, 9, 
    16, 31, 30, 29, 10, 
    15, 14, 13, 12, 11, 

The time complexity is actually O(3nxm), with the first O(1nxm) being for inputting the elements into the input matrix; the second O(1nxm) being for rotating all the elements in the matrix, in the called function, the third O(1nxm) being for printing out all the elements in the output matrix, in the called function. The coefficient (multiplicand of 3) is usually omitted, to quote the time complexity as O(nxm).

The space complexity is actually O(2nxm), with the first O(1nxm) being for the input matrix space, and the second O(nxm) being for the output matrix space. The coefficient (multiplicand of 2) is usually omitted, to quote the space complexity as O(nxm).

Thanks for reading.