Given a square matrix mat[][] of dimensions N * N, the task is to print the matrix that can be obtained after swapping the laterally inverted images of the upper and lower triangular halves of a given matrix.
Consider the matrix mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
The lateral image of the lower triangular half of the matrix4
7 8The lateral image of the upper triangular half of the matrix
6
3 2Therefore, following rearrangement of the matrix needs to be performed
1 2 3 1 8 7
4 5 6 to 6 5 4
7 8 9 3 2 9
Examples:
Input: mat[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Output:
1 8 7
6 5 4
3 2 9
Explanation:1 2 3 6 5 4
1 8 7 to 7 8 9
4 5 6 3 2 9Input: mat[][] = {{1, 2}, {4, 5}}
Output:
1 4
2 5
Approach: Follow the steps below to solve the problem:
- Initialize an array of vectors, upDiagonal, and lowDiagonal, to store the elements of the matrix elements from the lower and upper triangular halves respectively.
- Traverse the given matrix using variables i and j for rows and column respectively and perform the following steps:
- If the current element is on the principal diagonal, then continue from this iteration.
- Otherwise, if the current element is present in the upper triangular half, then add this element to upDiagonal at index abs(i – j).
- Otherwise, add the current element to lowDiagonal at index abs(i – j).
- Now, again traverse the matrix and replace any element present in the upper-half with the element from the end of the lower-half and vice versa.
- After completing the above steps, print the resultant matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixvoid ReverseSwap(vector<vector<int> >& mat, int n){ // Store the matrix elements from // upper & lower triangular halves vector<int> lowerEle[n]; vector<int> upperEle[n]; int index; // Traverse the matrix mat[][] for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Find the index index = abs(i - j); // If current element lies // on the principal diagonal if (i == j) { continue; } // If current element lies // below the principal diagonal else if (j < i) { lowerEle[index].push_back( mat[i][j]); } // If current element lies // above the principal diagonal else { upperEle[index].push_back( mat[i][j]); } } } // Traverse again to swap values for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // Find the index index = abs(i - j); // Principal diagonal if (i == j) { continue; } // Below main diagonal else if (j < i) { mat[i][j] = upperEle[index].back(); upperEle[index].pop_back(); } // Above main diagonal else { mat[i][j] = lowerEle[index].back(); lowerEle[index].pop_back(); } } } // Traverse the matrix and print for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << mat[i][j] << " "; } cout << endl; }}// Driver Codeint main(){ // Given Matrix mat[][] vector<vector<int> > mat = { { 1, 2 }, { 4, 5 } }; int N = mat.size(); // Swap the upper and lower // triangular halves ReverseSwap(mat, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixstatic void ReverseSwap(int[][] mat, int n){ // Store the matrix elements from // upper & lower triangular halves int[] lowerEle = new int[n]; int[] upperEle = new int[n]; int index; // Traverse the matrix mat[][] for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // Find the index index = Math.abs(i - j); // If current element lies // on the principal diagonal if (i == j) { continue; } // If current element lies // below the principal diagonal else if (j < i) { lowerEle[index] = mat[i][j]; } // If current element lies // above the principal diagonal else { upperEle[index] = mat[i][j]; } } } // Traverse again to swap values for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // Find the index index = Math.abs(i - j); // Principal diagonal if (i == j) { continue; } // Below main diagonal else if (j < i) { mat[i][j] = upperEle[index]; } // Above main diagonal else { mat[i][j] = lowerEle[index--]; } } } // Traverse the matrix and print for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.print(mat[i][j] + " "); } System.out.println(); }}// Driver Codepublic static void main(String[] args){ // Given Matrix mat[][] int[][] mat = new int[][]{ { 1, 2 }, { 4, 5 } }; int N = mat.length; // Swap the upper and lower // triangular halves ReverseSwap(mat, N);}}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approach# Function to swap laterally inverted# images of upper and lower triangular# halves of a given matrixdef ReverseSwap(mat, n): # Store the matrix elements from # upper & lower triangular halves lowerEle = [[] for i in range(n)] upperEle = [[] for i in range(n)] index = 0 # Traverse the matrix mat[][] for i in range(n): for j in range(n): # Find the index index = abs(i - j) # If current element lies # on the principal diagonal if (i == j): continue # If current element lies # below the principal diagonal elif (j < i): lowerEle[index].append(mat[i][j]) # If current element lies # above the principal diagonal else: upperEle[index].append(mat[i][j]) # Traverse again to swap values for i in range(n): for j in range(n): # Find the index index = abs(i - j) # Principal diagonal if (i == j): continue # Below main diagonal elif (j < i): mat[i][j] = upperEle[index][-1] del upperEle[index][-1] # Above main diagonal else: mat[i][j] = lowerEle[index][-1] del lowerEle[index][-1] # Traverse the matrix and pr for i in range(n): for j in range(n): print (mat[i][j], end = " ") print()# Driver Codeif __name__ == '__main__': # Given Matrix mat[][] mat = [ [ 1, 2 ], [ 4, 5 ] ] N = len(mat) # Swap the upper and lower # triangular halves ReverseSwap(mat, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixstatic void ReverseSwap(int[,] mat, int n){ // Store the matrix elements from // upper & lower triangular halves int[] lowerEle = new int[n]; int[] upperEle = new int[n]; int index; // Traverse the matrix mat[][] for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // Find the index index = Math.Abs(i - j); // If current element lies // on the principal diagonal if (i == j) { continue; } // If current element lies // below the principal diagonal else if (j < i) { lowerEle[index] = mat[i, j]; } // If current element lies // above the principal diagonal else { upperEle[index] = mat[i, j]; } } } // Traverse again to swap values for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { // Find the index index = Math.Abs(i - j); // Principal diagonal if (i == j) { continue; } // Below main diagonal else if (j < i) { mat[i, j] = upperEle[index]; } // Above main diagonal else { mat[i, j] = lowerEle[index--]; } } } // Traverse the matrix and print for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { Console.Write(mat[i, j] + " "); } Console.WriteLine(); }}// Driver Codestatic public void Main(){ // Given Matrix mat[][] int[,] mat = new int[,]{ { 1, 2 }, { 4, 5 } }; int N = mat.GetLength(0); // Swap the upper and lower // triangular halves ReverseSwap(mat, N);}}// This code is contributed by Dharanendra L V |
Javascript
<script>// JavaScript program for the above approach// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixfunction ReverseSwap(mat,n){ // Store the matrix elements from // upper & lower triangular halves let lowerEle = new Array(n); let upperEle = new Array(n); let index; // Traverse the matrix mat[][] for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { // Find the index index = Math.abs(i - j); // If current element lies // on the principal diagonal if (i == j) { continue; } // If current element lies // below the principal diagonal else if (j < i) { lowerEle[index] = mat[i][j]; } // If current element lies // above the principal diagonal else { upperEle[index] = mat[i][j]; } } } // Traverse again to swap values for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { // Find the index index = Math.abs(i - j); // Principal diagonal if (i == j) { continue; } // Below main diagonal else if (j < i) { mat[i][j] = upperEle[index]; } // Above main diagonal else { mat[i][j] = lowerEle[index--]; } } } // Traverse the matrix and print for(let i = 0; i < n; i++) { for(let j = 0; j < n; j++) { document.write(mat[i][j] + " "); } document.write("<br>"); }}// Driver Codelet mat=[[1, 2],[ 4, 5 ]];let N = mat.length;// Swap the upper and lower// triangular halvesReverseSwap(mat, N);// This code is contributed by patel2127</script> |
Output
1 4 2 5
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Optimised Approach: Without space
We will traverse only the upper triangular half and swap elements of the upper triangular half with the lower triangular half. But how we can access elements of the lower triangular half if we are only traversing the upper triangular half?
Because if the index of any element in the upper triangular half is “i,j” then “j,i”will be the index of the corresponding element in the lower triangular half.
Code-
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixvoid swapUpperToLower(vector<vector<int> > mat,int n){ // Loop for swap the elements of matrix. for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } // Loop for print the matrix elements. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << mat[i][j] << " "; cout << endl; }}// Driver function to run the programint main(){// Given Matrix mat[][] vector<vector<int> > mat = { { 1, 2 }, { 4, 5 } }; int n = mat.size(); // Swap the upper and lower // triangular halves swapUpperToLower(mat,n); return 0;} |
Java
import java.util.Arrays;public class Main { // Function to swap laterally inverted // images of upper and lower triangular // halves of a given matrix static void swapUpperToLower(int[][] mat) { int n = mat.length; // Loop to swap the elements of the matrix for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } // Loop to print the matrix elements for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) System.out.print(mat[i][j] + " "); System.out.println(); } } // Driver function to run the program public static void main(String[] args) { // Given Matrix mat[][] int[][] mat = { {1, 2}, {4, 5} }; // Swap the upper and lower triangular halves swapUpperToLower(mat); }} |
Javascript
// JavaScript program for the above approach// Function to swap laterally inverted// images of upper and lower triangular// halves of a given matrixfunction swapUpperToLower(mat, n) { // Loop to swap the elements of the matrix for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { const temp = mat[i][j]; mat[i][j] = mat[j][i]; mat[j][i] = temp; } } // Loop to print the matrix elements for (let i = 0; i < n; i++) { let row = ''; for (let j = 0; j < n; j++) { row += mat[i][j] + ' '; } console.log(row); }}// Driver function to run the programconst mat = [ [1, 2], [4, 5]];const n = mat.length;// Swap the upper and lower// triangular halvesswapUpperToLower(mat,n); |
Output-
1 4
2 5
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!