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

Reversing an Array using Two Pointers in O(n) Time and O(n) Space
A row or column of a matrix (2D array) can be considered as an array.

Two pointers refer to left (i) and right (j) indexes, such that left points at the start of the array and right points to the end of the array, initially.

While the left (or top) pointer is less than the right (or bottom) pointer, swap the elements at these two positions. After each swap, increment the left pointer and decrement the right pointer to move towards the center of the array. This will swap all the elements in the first half with their corresponding elements in the second half. If the number of elements in the array is odd, then the center (middle) element will not be swapped.

O(N) space refers to the array space. The time complexity is actually O(½N), but the coefficient (multiplicand of ½) is usually omitted to quote a time complexity of O(N).

Problem

Given a matrix mat[][], rotate the matrix by 180 degrees. Note: Rotating 180^° clockwise or anticlockwise gives the same result. Please note that the order of the resulting matrix is going to remain the same.

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: 
                   [[20  19  18  17  16]
                    [15  14  13  12  11]
                    [10  9   8   7   6 ]
                    [5   4   3   2   1]]

Note

Notice that the resulting (output) matrix is the reversal of each row and each column, from the given matrix. So, use the technique of reversing a row, and reversing a column. Revering a column is fundamentally the same as reversing a row, actually in O(½N) time. Reversing the whole matrix by only rows or by only columns, actually takes O(½N x M) time. All the rows can be reversed first before the columns are reversed, in order to rotate the matrix by 180 degrees.

Solution Strategy

Use the two-pointers technique to reverse all the rows and then use the same two-pointers technique to reverse all the columns. That should actually take O(2 x ½N x M) time, equals to O(N x M).

The program

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

#include <stdio.h>

// Helper function to swap two numbers
void swap(int *a, int *b) {
    int temp = *a;    //temporary single variable and not temporary array
    *a = *b;
    *b = temp;
}

void rotateMatrix180(int mat[][5], int n, int m) {
    //reverse rows
    for (int i=0; i < n; i++) {
        int left = 0, right = m - 1;

        // Iterate till left would almost equal right
        while (left < right) {
            swap(&mat[i][left], &mat[i][right]);

            // Increment the left pointer
            left++;
            // Decrement the right pointer
            right--;
        }
    }

    //reverse columns
    for (int j=0; j < m; j++) {
        int top = 0, bottom = n - 1;

        // Iterate till top would almost equal bottom
        while (top < bottom) {
            swap(&mat[top][j], &mat[bottom][j]);   //note squares for j, top and bottom

            // Increment the top pointer
            top++;
            // Decrement the bottom pointer
            bottom--;
        }
    }

    //print result
    for (int i=0; i < n; i++) {
        for (int j=0; j < m; j++) {
            printf("%i, ", mat[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}};
      
    rotateMatrix180(mat, n, m);

    return 0;
}

The output is:

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

Note the use of the swap() helper function, where int *a from the swap() function corresponds to &mat[i][left] or &mat[top][j] in the called function; and int *b from the swap() function corresponds to &mat[i][right] or &mat[bottom][j] in the called function.

The time complexity is actually O(3nxm), with the first O(nxm) for populating the 2D input array; the second for the 180 degrees rotation (reversals) of all the elements; and the third for the printing of the transformed array. However, the coefficient (multiplicand of 3) is usually omitted, to quote the time complexity as O(n x m).

The space complexity is O(nxm), for the input matrix, which is the same as the matrix in the called function (same reference).

Thanks for reading.