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

Two Pointers Technique

Two pointers refer to left (i) and right (j) indexes, such that left points to the start of the array and right points to the end of the array, initially. The opposite pointers move towards the center of the array during iterations, until a condition is met.

Major Diagonal and Minor Diagonal

The terms "Major Diagonal" and "Minor Diagonal" are applicable only to square matrices.

Major Diagonal

Major Diagonal (Primary/Main Diagonal) are elements that appear from the top-left corner to the bottom-right corner of the matrix, where the row (i) and column (j) indexes are the same.

Minor Diagonal

Minor Diagonal (Secondary Diagonal) are elements that appear from the top-right corner to the bottom-left corner, where the sum of the row (i) and column (j) indexes, equals one less than the matrix length (or width, which are the same for a square matrix); zero based indexing.

Problem

Given a square matrix mat[][], swap the elements of its major and minor diagonals, in O(n) time.

Example 1: 
Input: mat[][] = [[0, 1, 2],
                  [3, 4, 5],
                  [6, 7, 8]]

Note:

Input Major Diagonal = [0, 4, 8]:
Looking at the input matrix, when the element is 0, i = j = 0; when the element is 4, i = j = 1; and when the element is 8, i = j = 2.

Input Minor Diagonal = [2, 4, 6]
Looking at the input matrix, when the element is 2, i = 0 and j = 2, making i+j=0+2=2=3-1; when the element is 4, i = 1 and j = 1, making i+j=1+1=2=3-1; when the element is 8, i = 2 and j = 0, making i+j=2+0=2=3-1. And 2 = 3 - 1 = m-1 = n-1 (square matrix).

Output : [[2, 1, 0],
          [3, 4, 5],
          [8, 7, 6]]

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

Input Major Diagonal = [0, 5, 10, 15]:
Looking at the input matrix, when the element is 0, i = j = 0; when the element is 5, i = j = 1; when the element is 10, i = j = 2; when the element is 15, i = j = 3.

Input Minor Diagonal = [3, 6, 9, 12]
Looking at the input matrix, when the element is 3, i = 0 and j = 3, making i+j=0+3=3=4-1; when the element is 6, i = 1 and j = 2, making i+j=1+3=3=4-1; when the element is 9, i = 2 and j = 1, making i+j=2+1=3=4-1; when the element is 12, i = 3 and j = 0, making i+j=3+0=3=4-1. And 3 = 4 - 1 = m-1 = n-1 (square matrix).

Output : [[3,  1,  2,  0 ],
          [4,  6,  5,  7 ],
          [8,  10, 9,  11],
          [15, 13, 14, 12]]

Also note that if the width which is the same as the length for a square matrix, is odd, the middle/center element is not swapped. If it is even, there is no really middle/center element and all the elements of both diagonals are swapped.

Solution in O(n) Time

Both diagonals form an X shape. Each diagonal should be imagined as an array of n elements, where this n is the same as the width or length (height) of the square matrix.

Special Two-Pointers Technique

The two-pointers technique used here, is not exactly what is described above. Here, at the beginning, the left pointer points to the X top-left element at coordinates [0][0], and the right pointer points to the X top-right element at coordinates [0][n-1]; zero based indexing.

The swapping begins at the top line, continues, pass the middle/center point, and continues until the bottom line.

After each swap, the j coordinate (index) of the previous major diagonal element is increased by one, and the j coordinate of the previous minor diagonal element is reduced by one. The i coordinate after each swap is increased by 1. This continues, go pass the middle/center point, and continues until just after the j coordinate of the last element of the major diagonal is n-1 or the j coordinate of the last element of the minor diagonal is 0.

The incrementing of the j coordinate of each element of the major diagonal is done naturally by a for-loop. For the major diagonal, when the j coordinate (index) increases by 1, the i coordinate should also increase by one, for the next element one column ahead and one row below. The coordinates (indexes) of each element in the major diagonal, which is the left pointer, is given by,

    mat[j][j]

instead of mat[i][j], to avoid increasing i independently. The i and j coordinates (indexes) of the corresponding minor diagonal element, which is the right pointer, on the same horizontal line, is given by

    mat[j][n-1-j]

where j here is the same as i, since a square matrix is concerned, and for each iteration, the column shift is the same as the row shift of one unit; and n is the width or length (height) of the square matrix.

The program

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

#include <stdio.h>

void swapDiagonals(int mat[][4], int n) {
    for (int j=0; j < n; j++) {
       // swap major and minor diagonal elements.
        int temp = mat[j][j];    //temporary single variable and not temporary array
        mat[j][j] = mat[j][n - j - 1];
        mat[j][n - j - 1] = temp;
    }

    //print result
    for (int i=0; i < n; i++) {
        for (int j=0; j < n; j++) {
            printf("%i, ", mat[i][j]);
        }
        printf("\n");
    }
}

int main(int argc, char **argv) 
{
    int n=4;
    int mat[4][4] = {{0,  1,  2,  3},
                     {4,  5,  6,  7},
                     {8,  9,  10, 11},
                     {12, 13, 14, 15}};
      
    swapDiagonals(mat, n);

    return 0;
}

The output is:

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

The time complexity is actually O(n) and not O(2n) for either of the diagonals. Though both diagonal elements are addressed, they are addressed in one iteration and not two iterations.

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

Thanks for reading.