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 square matrix, the task is to rotate its elements clockwise by one step.

Example 1: 
Input:  mat[][] = [[1    2]
                   [4   3]]
                   
Output: 
                [4    1]
                [3    2]]

Example 2: 
Input:  mat[][] = [[1    2    3]
                   [8    9    4] 
                   [7    6    5]]
                   
Output: 
                [8    1    2]
                [7    9    3]
                [6    5    4]]

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

Solution in O(n²) Time

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 square ring of elements, starting from the outermost ring (and left-top). 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 elements in the matrix is odd, then the innermost element will not change its position. In that case, just copy the innermost element from the input matrix to the innermost position of the output (destination) 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
    }
    
    //If number of elements is odd,
    //then just copy the center (middle) element
    //after above execution
    if (p % 2 == 1)
        rotmat[p/2][q/2] = mat[p/2][q/2];
    
    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=2, m=2;
    int mat[2][2] = {{1, 2}, 
                     {4, 3}};
      
    rotateMatrix1(mat, n, m);
*/
/*
    int n2=3, m2=3;
    int mat2[3][3] = {{1, 2, 3}, 
                     {8, 9, 4}, 
                     {7, 6, 5}};
                    
    rotateMatrix1(mat2, n2, m2);
*/
/*
    int n3=4, m3=4;
    int mat3[4][4] ={{1,  2,  3,  4}, 
                     {12, 13, 14, 5}, 
                     {11, 16, 15, 6},
                     {10, 9,  8,  7}};
      
    rotateMatrix1(mat3, n3, m3);
*/
    return 0;
}

Remove the first pair of block quote markers (/* and */), and make the first parameter of the rotateMatrix1() function, "mat[][2]" . In this case, the output should be:

    4, 1, 
    3, 2, 

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[][3]" . In this case, the output should be:

    8, 1, 2, 
    7, 9, 3, 
    6, 5, 4, 

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[][4]" . In this case, the output should be:

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

The time complexity is actually O(3n²), with the first O(1n²) being for inputting the elements into the input matrix; the second O(1n²) being for rotating all the elements in the matrix, in the called function; the third O(1n²) 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(n²).

The space complexity is actually O(2n²), with the first O(1n²) being for the input matrix space, and the second O(1n²) being for the output matrix space. The coefficient (multiplicand of 2) is usually omitted, to quote the space complexity as O(n²). The O(1) time or O(1) space to create the empty matrix in the called function is ignored.

Thanks for reading.