Given a lower triangular matrix Mat[][], the task is to store the matrix using row-major mapping.
Lower Triangular Matrix: A Lower Triangular Matrix is a square matrix in which the lower triangular part of a matrix consists of non-zero elements and the upper triangular part consists of 0s. The Lower Triangular Matrix for a 2D matrix Mat[][] is mathematically defined as:
- If i < j, set Mat[i][j] = 0.
- If i >= j, set Mat[i][j] > 0.
Illustration: Below is a 5×5 lower triangular matrix. In general, such matrices can be stored in a 2D array, but when it comes to matrices of large size, it is not a good choice because of its high memory consumption due to the storage of unwanted 0s.
Such a matrix can be implemented in an optimized manner.
The efficient way to store the lower triangular matrix of size N:
- Count of non-zero elements = 1 + 2 + 3 + … + N = N * (N + 1) /2.
- Count of 0s = N2 – (N * (N + 1) /2 = (N * (N – 1)/2.
Now let us see how to represent lower triangular matrices in our program. Notice that storing 0s must be avoided to reduce memory consumption. As calculated, for storing non-zero elements, N*(N + 1)/2 space is needed. Taking the above example, N = 5. Array of size 5 * (5 + 1)/2 = 15 is required to store the non-zero elements.
Now, elements of the 2D matrix can be stored in a 1D array, row by row, as shown below:
Apart from storing the elements in an array, a procedure for extracting the element corresponding to the row and column number is also required.
Using Row-Major Mapping for storing lower triangular matrix, the element at index Mat[i][j] can be represented as:
Index of Mat[i][j] matrix in the array A[] = [i*(i – 1)/2 + j – 1]
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Dimensions of a matrixstatic int N = 5;// Structure of the efficient matrixclass Matrix { public: int* A; int size;};// Function to set the// values in the Matrixvoid Set(Matrix mat, int i, int j, int x){ if (i >= j) mat.A[i * (i - 1) / 2 + j - 1] = x;}// Function to store the// values in the Matrixint Get(Matrix mat, int i, int j){ if (i >= j) return mat.A[i * (i - 1) / 2 + j - 1]; return 0;}// Function to display the// elements of the matrixvoid Display(Matrix mat){ int i, j; // Traverse the matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { if (i >= j) cout << mat.A[i * (i - 1) / 2 + j - 1] << " "; else cout << 0 << " "; } cout << endl; }}// Function to generate an efficient matrixMatrix createMat(vector<vector<int> >& Mat){ // Declare efficient Matrix Matrix mat; // Initialize the Matrix mat.size = N; mat.A = new int[(mat.size * (mat.size + 1)) / 2]; int i, j; // Set the values in matrix for (i = 1; i <= mat.size; i++) for (j = 1; j <= mat.size; j++) Set(mat, i, j, Mat[i - 1][j - 1]); // Return the matrix return mat;}// Driver Codeint main(){ vector<vector<int> > Mat = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Stores the efficient matrix Matrix mat = createMat(Mat); // Print the Matrix Display(mat); return 0;}// This code is contributed by Tapesh (tapeshdua420) |
C
// C program for the above approach#include <stdio.h>#include <stdlib.h>// Dimensions of a matrixconst int N = 5;// Structure of the efficient matrixstruct Matrix { int* A; int size;};// Function to set the// values in the Matrixvoid Set(struct Matrix* mat, int i, int j, int x){ if (i >= j) mat->A[i * (i - 1) / 2 + j - 1] = x;}// Function to store the// values in the Matrixint Get(struct Matrix mat, int i, int j){ if (i >= j) { return mat.A[i * (i - 1) / 2 + j - 1]; } else { return 0; }}// Function to display the// elements of the matrixvoid Display(struct Matrix mat){ int i, j; // Traverse the matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { if (i >= j) { printf("%d ", mat.A[i * (i - 1) / 2 + j - 1]); } else { printf("0 "); } } printf("\n"); }}// Function to generate an efficient matrixstruct Matrix createMat(int Mat[N][N]){ // Declare efficient Matrix struct Matrix mat; // Initialize the Matrix mat.size = N; mat.A = (int*)malloc( mat.size * (mat.size + 1) / 2 * sizeof(int)); int i, j; // Set the values in matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { Set(&mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat;}// Driver Codeint main(){ int Mat[5][5] = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Stores the efficient matrix struct Matrix mat = createMat(Mat); // Print the Matrix Display(mat); return 0;} |
Java
// Java program for the above approachclass GFG{ // Dimensions of a matrixstatic int N = 5;// Structure of the efficient matrixstatic class Matrix { int[] A; int size;};// Function to set the// values in the Matrixstatic void Set(Matrix mat, int i, int j, int x){ if (i >= j) mat.A[i * (i - 1) / 2 + j - 1] = x;}// Function to store the// values in the Matrixstatic int Get(Matrix mat, int i, int j){ if (i >= j) { return mat.A[i * (i - 1) / 2 + j - 1]; } else { return 0; }}// Function to display the// elements of the matrixstatic void Display(Matrix mat){ int i, j; // Traverse the matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { if (i >= j) { System.out.printf("%d ", mat.A[i * (i - 1) / 2 + j - 1]); } else { System.out.printf("0 "); } } System.out.printf("\n"); }}// Function to generate an efficient matrixstatic Matrix createMat(int Mat[][]){ // Declare efficient Matrix Matrix mat = new Matrix(); // Initialize the Matrix mat.size = N; mat.A = new int[(mat.size*(mat.size + 1)) / 2]; int i, j; // Set the values in matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { Set(mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat;}// Driver Codepublic static void main(String[] args){ int Mat[][] = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Stores the efficient matrix Matrix mat = createMat(Mat); // Print the Matrix Display(mat);}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Dimensions of a matrixN = 5# Structure of the efficient matrixclass Matrix: def __init__(self, size): self.size = size self.A = [None] * (self.size)# Function to set the# values in the Matrixdef Set(mat, i, j, x): if i >= j: mat.A[i * (i - 1) // 2 + j - 1] = x# Function to store the# values in the Matrixdef get(mat, i, j): if i >= j: return mat.A[i * (i - 1) // 2 + j - 1] return 0# Function to display the# elements of the matrixdef display(mat): # Traverse the matrix for i in range(1, mat.size + 1): for j in range(1, mat.size + 1): if i >= j: print(mat.A[i * (i - 1) // 2 + j - 1], end=" ") else: print(0, end=" ") print()# Function to generate an efficient matrixdef create_matrix(Mat): # Declare efficient Matrix mat = Matrix(N) # Initialize the Matrix mat.A = [None] * ((mat.size * (mat.size+1)) // 2) # Set the values in matrix for i in range(1, mat.size + 1): for j in range(1, mat.size + 1): Set(mat, i, j, Mat[i - 1][j - 1]) # Return the matrix return matif __name__ == '__main__': Mat = [[1, 0, 0, 0, 0], [1, 2, 0, 0, 0], [1, 2, 3, 0, 0], [1, 2, 3, 4, 0], [1, 2, 3, 4, 5]] mat = create_matrix(Mat) display(mat)# This code is contributed by Tapesh (tapeshdua420) |
C#
// C# program for the above approachusing System;public class GFG{ // Dimensions of a matrix static int N = 5; // Structure of the efficient matrix class Matrix { public int[] A; public int size; }; // Function to set the // values in the Matrix static void Set(Matrix mat, int i, int j, int x) { if (i >= j) mat.A[i * (i - 1) / 2 + j - 1] = x; } // Function to store the // values in the Matrix static int Get(Matrix mat, int i, int j) { if (i >= j) { return mat.A[i * (i - 1) / 2 + j - 1]; } else { return 0; } } // Function to display the // elements of the matrix static void Display(Matrix mat) { int i, j; // Traverse the matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { if (i >= j) { Console.Write("{0} ", mat.A[i * (i - 1) / 2 + j - 1]); } else { Console.Write("0 "); } } Console.Write("\n"); } } // Function to generate an efficient matrix static Matrix createMat(int [,]Mat) { // Declare efficient Matrix Matrix mat = new Matrix(); // Initialize the Matrix mat.size = N; mat.A = new int[(mat.size*(mat.size + 1)) / 2]; int i, j; // Set the values in matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { Set(mat, i, j, Mat[i - 1,j - 1]); } } // Return the matrix return mat; } // Driver Code public static void Main(String[] args) { int [,]Mat = { { 1, 0, 0, 0, 0 }, { 1, 2, 0, 0, 0 }, { 1, 2, 3, 0, 0 }, { 1, 2, 3, 4, 0 }, { 1, 2, 3, 4, 5 } }; // Stores the efficient matrix Matrix mat = createMat(Mat); // Print the Matrix Display(mat); }}// This code is contributed by 29AjayKumar |
Javascript
// JavaScript program for the above approachlet N = 5;class Matrix{ A = new Array(); size; constructor(){ }}function Set(mat, i, j, x){ if (i >= j){ mat.A[i * (i - 1) / 2 + j - 1] = x; }}function Get(mat, i, j){ if (i >= j) { return mat.A[i * (i - 1) / 2 + j - 1]; } else { return 0; }}function Display(mat){ let i, j; // Traverse the matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { if (i >= j) { console.log(mat.A[i * (i - 1) / 2 + j - 1] + " "); } else { console.log("0 "); } } console.log("<br>"); }}function createMat(Mat){ var mat = new Matrix(); mat.size = N; mat.A = new Array((mat.size*(mat.size + 1))/2); let i, j; // Set the values in matrix for (i = 1; i <= mat.size; i++) { for (j = 1; j <= mat.size; j++) { Set(mat, i, j, Mat[i - 1][j - 1]); } } // Return the matrix return mat;}let Mat = [ [1, 0, 0, 0, 0], [1, 2, 0, 0, 0], [1, 2, 3, 0, 0], [1, 2, 3, 4, 0], [1, 2, 3, 4, 5] ];var mat = createMat(Mat);Display(mat);// This code is contributed by lokesh. |
Output:
1 0 0 0 0 1 2 0 0 0 1 2 3 0 0 1 2 3 4 0 1 2 3 4 5
Time Complexity: O(N2)
Auxiliary Space: O(N2)
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!
