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

Problem

Given an image represented by n x m matrix, rotate the image by 90 degrees in counterclockwise direction. Please note that the order of the resulting matrix is going to change from n x m to m x n.

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

Solution in O(n x m) Time

In this rotation, the first row becomes the first column going upwards; the second row becomes the second column going upwards; the third row becomes the third column going upwards; and so on.

For i and j coordinate zero based indexing, notice in the above output that each element undergoes the following exchange:

    mat[i][j] to rotmat[m - j - 1][i]

where mat is the input matrix and rotmat is the output matrix. The -1 in [m - j - 1] is for the zero based indexing, since m is the total number of columns in the given matrix. The reader should take some values in the input matrix above and use this rotation statement to confirm the rotation statement, with the output matrix.

Algorithm

In the called function declare an empty m-by-n matrix. Iterate over all the elements in the given matrix, applying the above transformation statement. Use two for-loops, one nested.

The program

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

#include <stdio.h>

void rotateAMatrix90(int mat[][5], int n, int m) {
    int rotmat[m][n];    //rotated matrix

    for (int i=0; i < n; i++) {
        for (int j=0; j < m; j++) {
            rotmat[m - j - 1][i] = mat[i][j];
        }
    }

    for (int i=0; i < m; i++) {    // row to column
        for (int j=0; j < n; j++) {    //column to row
            printf("%i, ", rotmat[i][j]);
        }
        printf("\n");
    }
}

int main(int argc, char **argv) 
{
    int n=4, m=5;
    int mat[4][5] = {{1,  2,  3,  4,  5 },
                     {6,  7,  8,  9,  10},
                     {11, 12, 13, 14, 15},
                     {16, 17, 18, 19, 20}};
      
    rotateAMatrix90(mat, n, m);

    return 0;
}

The output is:

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

The time complexity is actually O(2nxm), with the first O(nxm) being for inputting the elements into the input matrix; the second O(nxm) being for rotating all the elements in the matrix, in the called function. The coefficient (multiplicand of 2) is usually omitted, to quote the time complexity as O(n x m).

The space complexity is actually O(2nxm), with the first O(nxm) 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(n x m).

Thanks for reading.