Given a lower triangular matrix M[][] of dimension N * N, the task is to convert it into a one-dimensional array by storing only non-zero elements.
Examples:
Input: M[][] = {{1, 0, 0, 0}, {2, 3, 0, 0}, {4, 5, 6, 0}, {7, 8, 9, 10}}
Output:
Row-wise: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Column-wise: {1, 2, 4, 7, 3, 5, 8, 6, 9, 10}
Explanation: All the non-zero elements of the matrix are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Arranging these elements in row-wise manner in a 1D array generates the sequence {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
Arranging these elements in column-wise manner in a 1D array generates the sequence {1, 2, 4, 7, 3, 5, 8, 6, 9, 10}.Input: M[][] = {{1, 0, 0, }, {2, 3, 0}, {4, 5, 6}}
Output:
Row-wise: {1, 2, 3, 4, 5, 6}
Column-wise: {1, 2, 4, 3, 5, 6}
Approach:To convert a 2-dimensional matrix to a 1-dimensional array following two methods are used:
- In this method, adjacent elements of a row are placed next to each other in the array.
- The following formula is used to find out the respective positions of the non-zero elements of the lower triangular matrix in the 1-dimensional array.
Index of matrix element at position (i, j) = ((i * (i – 1))/2 + j – 1)
where 1 ? i, j ? N and i ? j
- In this method, consecutive elements of a column are placed adjacently in the array.
- The following formula is used to find out the respective positions of the non-zero elements of the lower triangular matrix in the 1-dimensional array.
Index of matrix element at position (i, j) = (N * (j – 1) – ((j – 2) * (j – 1))/2) + (i – j)
where 1 ? i, j ? N and i ? j.
Follow the steps below to solve the problem:
- Initialize an array, say A[], to store the non-zero elements of the matrix.
- Traverse the matrix M[][] and find the index of non-zero elements of the matrix in the array A[] using the formula for row-major mapping and insert each non-zero element in the array A[].
- After completing the above step, print the array A[] for row-major mapping.
- Again, traverse the matrix M[][] and find the index of non-zero elements of the matrix in the array A[] using the formula for column-major mapping and insert each non-zero element in the array A[].
- After completing the above steps, print the array A[] for column-major mapping.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Class of Lower Triangular Matrixclass LTMatrix {private: // Size of Matrix int n; // Pointer int* A; // Stores the count of non-zero // elements int tot;public: // Constructor LTMatrix(int N) { this->n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2]; } // Destructor ~LTMatrix() { delete[] A; } // Function to display array void Display(bool row = true); // Function to generate array // in Row - Major order void setRowMajor(int i, int j, int x); // Function to generate array // in Column - Major order void setColMajor(int i, int j, int x); // Function to find size of array int getN() { return n; }};// Function to generate array from// given matrix by storing elements// in column major ordervoid LTMatrix::setColMajor(int i, int j, int x){ if (i >= j) { int index = (n * (j - 1) - (((j - 2) * (j - 1)) / 2)) + (i - j); A[index] = x; }}// Function to generate array from// given matrix by storing elements// in row major ordervoid LTMatrix::setRowMajor(int i, int j, int x){ if (i >= j) { int index = (i * (i - 1)) / 2 + j - 1; A[index] = x; }}// Function to display array elementsvoid LTMatrix::Display(bool row){ for (int i = 0; i < tot; i++) { cout << A[i] << " "; } cout << endl;}// Function to generate and display// array in Row-Major Ordervoid displayRowMajor(int N){ LTMatrix rm(N); // Generate the array in the // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(2, 1, 2); rm.setRowMajor(2, 2, 3); rm.setRowMajor(3, 1, 4); rm.setRowMajor(3, 2, 5); rm.setRowMajor(3, 3, 6); rm.setRowMajor(4, 1, 7); rm.setRowMajor(4, 2, 8); rm.setRowMajor(4, 3, 9); rm.setRowMajor(4, 4, 10); // Display array elements // in row-major order cout << "Row-Wise:\n"; rm.Display();}// Function to generate and display// array in Column-Major Ordervoid displayColMajor(int N){ LTMatrix cm(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(2, 1, 2); cm.setColMajor(2, 2, 3); cm.setColMajor(3, 1, 4); cm.setColMajor(3, 2, 5); cm.setColMajor(3, 3, 6); cm.setColMajor(4, 1, 7); cm.setColMajor(4, 2, 8); cm.setColMajor(4, 3, 9); cm.setColMajor(4, 4, 10); // Display array elements // in column-major form cout << "Column-Wise:\n"; cm.Display(false);}// Driver Codeint main(){ // Size of row or column // of square matrix int N = 4; // Function Call for row major // mapping displayRowMajor(N); // Function Call for column // major mapping displayColMajor(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Class of Lower Triangular Matrix static class LTMatrix { // Size of Matrix static int n; // Pointer static int A[]; // Stores the count of non-zero // elements static int tot; // Constructor LTMatrix(int N) { this.n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2]; } // Function to display array elements static void Display(boolean row) { for (int i = 0; i < tot; i++) { System.out.print(A[i] + " "); } System.out.println(); } // Function to generate array from // given matrix by storing elements // in row major order static void setRowMajor(int i, int j, int x) { if (i >= j) { int index = (i * (i - 1)) / 2 + j - 1; A[index] = x; } } // Function to generate array from // given matrix by storing elements // in column major order static void setColMajor(int i, int j, int x) { if (i >= j) { int index = (n * (j - 1) - (((j - 2) * (j - 1)) / 2)) + (i - j); A[index] = x; } } // Function to find size of array static int getN() { return n; } } // Function to generate and display // array in Row-Major Order static void displayRowMajor(int N) { LTMatrix rm = new LTMatrix(N); // Generate the array in the // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(2, 1, 2); rm.setRowMajor(2, 2, 3); rm.setRowMajor(3, 1, 4); rm.setRowMajor(3, 2, 5); rm.setRowMajor(3, 3, 6); rm.setRowMajor(4, 1, 7); rm.setRowMajor(4, 2, 8); rm.setRowMajor(4, 3, 9); rm.setRowMajor(4, 4, 10); // Display array elements // in row-major order System.out.println("Row-Wise:"); rm.Display(false); } // Function to generate and display // array in Column-Major Order static void displayColMajor(int N) { LTMatrix cm = new LTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(2, 1, 2); cm.setColMajor(2, 2, 3); cm.setColMajor(3, 1, 4); cm.setColMajor(3, 2, 5); cm.setColMajor(3, 3, 6); cm.setColMajor(4, 1, 7); cm.setColMajor(4, 2, 8); cm.setColMajor(4, 3, 9); cm.setColMajor(4, 4, 10); // Display array elements // in column-major form System.out.println("Column-Wise:"); cm.Display(false); } // Driver Code public static void main(String[] args) { // Size of row or column // of square matrix int N = 4; // Function Call for row major // mapping displayRowMajor(N); // Function Call for column // major mapping displayColMajor(N); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach# Class of Lower Triangular Matrixclass LTMatrix: # Constructor def __init__(self, N): self.n = N; self.tot = N * (N + 1) // 2; self.A = [None] * (int(N * (N + 1) / 2)); # Function to display array elements def Display(self, row): for i in range(int(self.tot)): print(self.A[i], end = " ") print() # Function to generate array from # given matrix by storing elements # in row major order def setRowMajor(self, i, j, x): if (i >= j): index = (i * (i - 1)) // 2 + j - 1; self.A[index] = x; # Function to generate array from # given matrix by storing elements # in column major order def setColMajor(self, i, j, x): if (i >= j) : index =int((self.n * (j - 1) - (((j - 2) * (j - 1)) / 2)) + (i - j)); self.A[index] = x; # Function to find size of array def getN(self): return self.n; # Function to generate and display# array in Row-Major Orderdef displayRowMajor(N): rm = LTMatrix(N); # Generate the array in the # row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(2, 1, 2); rm.setRowMajor(2, 2, 3); rm.setRowMajor(3, 1, 4); rm.setRowMajor(3, 2, 5); rm.setRowMajor(3, 3, 6); rm.setRowMajor(4, 1, 7); rm.setRowMajor(4, 2, 8); rm.setRowMajor(4, 3, 9); rm.setRowMajor(4, 4, 10); # Display array elements # in row-major order print("Row-Wise:"); rm.Display(False);# Function to generate and display# array in Column-Major Orderdef displayColMajor(N): cm = LTMatrix(N); # Generate array in # column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(2, 1, 2); cm.setColMajor(2, 2, 3); cm.setColMajor(3, 1, 4); cm.setColMajor(3, 2, 5); cm.setColMajor(3, 3, 6); cm.setColMajor(4, 1, 7); cm.setColMajor(4, 2, 8); cm.setColMajor(4, 3, 9); cm.setColMajor(4, 4, 10); # Display array elements # in column-major form print("Column-Wise:"); cm.Display(False);# Driver Code# Size of row or column# of square matrixN = 4;# Function Call for row major# mappingdisplayRowMajor(N);# Function Call for column# major mappingdisplayColMajor(N);# This code is contributed by phasing17 |
C#
// C# program for the above approachusing System;public class LTMatrix { // Size of Matrix static int n; // Pointer static int[] A; // Stores the count of non-zero // elements static int tot; // Constructor public LTMatrix(int N) { n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2]; } // Function to display array elements public void Display(Boolean row) { for (int i = 0; i < tot; i++) { Console.Write(A[i] + " "); } Console.Write(""); } // Function to generate array from // given matrix by storing elements // in row major order public void setRowMajor(int i, int j, int x) { if (i >= j) { int index = (i * (i - 1)) / 2 + j - 1; A[index] = x; } } // Function to generate array from // given matrix by storing elements // in column major order public void setColMajor(int i, int j, int x) { if (i >= j) { int index = (n * (j - 1) - (((j - 2) * (j - 1)) / 2)) + (i - j); A[index] = x; } } // Function to find size of array static int getN() { return n; }}class GFG { // Class of Lower Triangular Matrix // Function to generate and display // array in Row-Major Order static void displayRowMajor(int N) { LTMatrix rm = new LTMatrix(N); // Generate the array in the // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(2, 1, 2); rm.setRowMajor(2, 2, 3); rm.setRowMajor(3, 1, 4); rm.setRowMajor(3, 2, 5); rm.setRowMajor(3, 3, 6); rm.setRowMajor(4, 1, 7); rm.setRowMajor(4, 2, 8); rm.setRowMajor(4, 3, 9); rm.setRowMajor(4, 4, 10); // Display array elements // in row-major order Console.WriteLine("Row-Wise:"); rm.Display(false); } // Function to generate and display // array in Column-Major Order static void displayColMajor(int N) { LTMatrix cm = new LTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(2, 1, 2); cm.setColMajor(2, 2, 3); cm.setColMajor(3, 1, 4); cm.setColMajor(3, 2, 5); cm.setColMajor(3, 3, 6); cm.setColMajor(4, 1, 7); cm.setColMajor(4, 2, 8); cm.setColMajor(4, 3, 9); cm.setColMajor(4, 4, 10); // Display array elements // in column-major form Console.WriteLine("\nColumn-Wise:"); cm.Display(false); } // Driver Code public static void Main() { // Size of row or column // of square matrix int N = 4; // Function Call for row major // mapping displayRowMajor(N); // Function Call for column // major mapping displayColMajor(N); }}// This code is contributed by Saurabh Jaiswal |
Javascript
// JS program for the above approach// Class of Lower Triangular Matrixclass LTMatrix { // Constructor constructor(N) { this.n = N; this.tot = N * (N + 1) / 2; this.A = new Array(Math.floor(N * (N + 1) / 2)); } // Function to display array elements Display(row) { for (var i = 0; i < this.tot; i++) { process.stdout.write(this.A[i] + " "); } console.log(); } // Function to generate array from // given matrix by storing elements // in row major order setRowMajor(i, j, x) { if (i >= j) { let index = (i * (i - 1)) / 2 + j - 1; this.A[index] = x; } } // Function to generate array from // given matrix by storing elements // in column major order setColMajor(i, j, x) { if (i >= j) { var index = Math.floor((this.n * (j - 1) - (((j - 2) * (j - 1)) / 2)) + (i - j)); this.A[index] = x; } } // Function to find size of array getN() { return this.n; }}// Function to generate and display// array in Row-Major Orderfunction displayRowMajor(N){ let rm = new LTMatrix(N); // Generate the array in the // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(2, 1, 2); rm.setRowMajor(2, 2, 3); rm.setRowMajor(3, 1, 4); rm.setRowMajor(3, 2, 5); rm.setRowMajor(3, 3, 6); rm.setRowMajor(4, 1, 7); rm.setRowMajor(4, 2, 8); rm.setRowMajor(4, 3, 9); rm.setRowMajor(4, 4, 10); // Display array elements // in row-major order console.log("Row-Wise:"); rm.Display(false);}// Function to generate and display// array in Column-Major Orderfunction displayColMajor(N){ let cm = new LTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(2, 1, 2); cm.setColMajor(2, 2, 3); cm.setColMajor(3, 1, 4); cm.setColMajor(3, 2, 5); cm.setColMajor(3, 3, 6); cm.setColMajor(4, 1, 7); cm.setColMajor(4, 2, 8); cm.setColMajor(4, 3, 9); cm.setColMajor(4, 4, 10); // Display array elements // in column-major form console.log("Column-Wise:"); cm.Display(false);}// Driver Code// Size of row or column// of square matrixlet N = 4;// Function Call for row major// mappingdisplayRowMajor(N);// Function Call for column// major mappingdisplayColMajor(N);// This code is contributed by phasing17 |
Output:
Row-Wise: 1 2 3 4 5 6 7 8 9 10 Column-Wise: 1 2 4 7 3 5 8 6 9 10
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!
