Efficient method to store a Lower Triangular Matrix using row-major mapping

0 0 9 minutes read

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 = N²– (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 matrix
static int N = 5;
 
// Structure of the efficient matrix
class Matrix {
  public:
  int* A;
  int size;
};
 
// Function to set the
// values in the Matrix
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
int 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 matrix
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)
        cout << mat.A[i * (i - 1) / 2 + j - 1]
        << " ";
      else
        cout << 0 << " ";
    }
    cout << endl;
  }
}
 
// Function to generate an efficient matrix
Matrix 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 Code
int 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 matrix
const int N = 5;
 
// Structure of the efficient matrix
struct Matrix {
    int* A;
    int size;
};
 
// Function to set the
// values in the Matrix
void 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 Matrix
int 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 matrix
void 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 matrix
struct 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 Code
int 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 approach
class GFG
{
   
// Dimensions of a matrix
static int N = 5;
 
// Structure of the efficient matrix
static class Matrix {
    int[] A;
    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) {
                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 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

Python3

# Python program for the above approach
 
# Dimensions of a matrix
N = 5
 
# Structure of the efficient matrix
class Matrix:
    def __init__(self, size):
        self.size = size
        self.A = [None] * (self.size)
 
# Function to set the
# values in the Matrix
def Set(mat, i, j, x):
    if i >= j:
        mat.A[i * (i - 1) // 2 + j - 1] = x
 
# Function to store the
# values in the Matrix
def 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 matrix
def 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 matrix
def 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 mat
 
 
if __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 approach
using 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 approach
 
let 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:

Time Complexity: O(N²)
Auxiliary Space: O(N²)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!