Given an upper triangular matrix M[][] of dimensions N * N, the task is to convert it into an one-dimensional array storing only non-zero elements from the matrix.
Examples:
Input: M[][] = {{1, 2, 3, 4}, {0, 5, 6, 7}, {0, 0, 8, 9}, {0, 0, 0, 10}}
Output: Row-wise: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Column-wise: {1, 2, 5, 3, 6, 8, 4, 7, 9, 10}
Explanation: All the non-zero elements of the matrix are {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}Input: M[][] = {{1, 2, 3, }, {0, 4, 5}, {0, 0, 6}}
Output: Row-wise: {1, 2, 3, 4, 5, 6}
Column-wise: {1, 2, 4, 3, 5, 6}
Explanation: All the non-zero elements of the matrix are {1, 2, 3, 4, 5, 6}
Approach: To convert given 2-dimensional matrix to a 1-dimensional array, following two methods are used:
Row – Major Order:
- In this method, elements are stored such that consecutive elements of a row are placed consecutively in the array.
ROW-MAJOR ORDER
- The following formula is used to find the correct position of non-zero matrix elements in the array:
Element present at index (i, j) in the matrix is placed at [N * (i – 1) – (i – 2) * (i -1) /2] + (j – i)
where 1 ? i, j ? N and i ? j
Column-Major Order:
- In this method, elements are stored such that consecutive elements of a column are placed consecutively in the array.
COLUMN-MAJOR ORDER
- The following formula is used to find out the correct position of non-zero matrix elements:
Element present at index (i, j) in the matrix is placed at [j * (j – 1) / 2] + i – 1
where 1 ? i, j ? N and i ? j.
Follow the steps below to solve the problem:
- Initialize an array A[] to store non-zero matrix elements.
- Traverse the matrix M[][].
- Find the correct indices of non-zero matrix elements in the array A[] using the above formulas.
- Place the non-zero elements at the correct indices of A[] accordingly.
- Finally, print the array A[] obtained.
Below is the implementation of the above approach:
C++
// C++ Program to convert a given// upper triangular matrix to 1D array#include <iostream>using namespace std;// Create a class of Upper// Triangular Matrixclass UTMatrix {private: // Size of Matrix int n; // Pointer int* A; // Stores count of // non-zero elements int tot;public: // Constructor UTMatrix(int N) { this->n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2]; } // Destructor ~UTMatrix() { 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 return size of array int getN() { return n; }};// Function to generate array from given matrix// by storing elements in column major ordervoid UTMatrix::setColMajor(int i, int j, int x){ if (i <= j) { int index = ((j * (j - 1)) / 2) + i - 1; A[index] = x; }}// Function to generate array from given matrix// by storing elements in row major ordervoid UTMatrix::setRowMajor(int i, int j, int x){ if (i <= j) { int index = (n * (i - 1) - (((i - 2) * (i - 1)) / 2)) + (j - i); A[index] = x; }}// Function to display array elementsvoid UTMatrix::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){ UTMatrix rm(N); // Generate array in // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(1, 2, 2); rm.setRowMajor(1, 3, 3); rm.setRowMajor(1, 4, 4); rm.setRowMajor(2, 2, 5); rm.setRowMajor(2, 3, 6); rm.setRowMajor(2, 4, 7); rm.setRowMajor(3, 3, 8); rm.setRowMajor(3, 4, 9); rm.setRowMajor(4, 4, 10); // Display array elements in // row-major order cout << "Row-Wise: "; rm.Display();}// Function to generate and display// array in Column-Major Ordervoid displayColMajor(int N){ UTMatrix cm(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(1, 2, 2); cm.setColMajor(1, 3, 3); cm.setColMajor(1, 4, 4); cm.setColMajor(2, 2, 5); cm.setColMajor(2, 3, 6); cm.setColMajor(2, 4, 7); cm.setColMajor(3, 3, 8); cm.setColMajor(3, 4, 9); cm.setColMajor(4, 4, 10); // Display array elements in // column-major form cout << "Column-wise: "; cm.Display(false);}// Driver Codeint main(){ // Size of row or column // of square matrix int N = 4; displayRowMajor(N); displayColMajor(N); return 0;} |
Java
// Java program to convert a given// upper triangular matrix to 1D array// Create a class of Upper// Triangular Matrixclass UTMatrix{ // Size of Matrixprivate int n;private int[] A = new int[n];// Stores count of// non-zero elementsprivate int tot;// Constructorpublic UTMatrix(int N){ this.n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2];}// Function to display arrayvoid Display(boolean row){ for(int i = 0; i < tot; i++) { System.out.print(A[i] + " "); } System.out.println();}// Function to generate array in// Row - Major ordervoid setRowMajor(int i, int j, int x){ if (i <= j) { int index = (n * (i - 1) - (((i - 2) * (i - 1)) / 2)) + (j - i); A[index] = x; }}// Function to generate array in// Column - Major ordervoid setColMajor(int i, int j, int x){ if (i <= j) { int index = ((j * (j - 1)) / 2) + i - 1; A[index] = x; }}// Function to return size of arrayint getN(){ return n;}}class GFG{// Function to generate and// display array in Row-Major Orderstatic void displayRowMajor(int N){ UTMatrix rm = new UTMatrix(N); // Generate array in // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(1, 2, 2); rm.setRowMajor(1, 3, 3); rm.setRowMajor(1, 4, 4); rm.setRowMajor(2, 2, 5); rm.setRowMajor(2, 3, 6); rm.setRowMajor(2, 4, 7); rm.setRowMajor(3, 3, 8); rm.setRowMajor(3, 4, 9); rm.setRowMajor(4, 4, 10); // Display array elements in // row-major order System.out.print("Row-Wise: "); rm.Display(false);}// Function to generate and display// array in Column-Major Orderstatic void displayColMajor(int N){ UTMatrix cm = new UTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(1, 2, 2); cm.setColMajor(1, 3, 3); cm.setColMajor(1, 4, 4); cm.setColMajor(2, 2, 5); cm.setColMajor(2, 3, 6); cm.setColMajor(2, 4, 7); cm.setColMajor(3, 3, 8); cm.setColMajor(3, 4, 9); cm.setColMajor(4, 4, 10); // Display array elements in // column-major form System.out.print("Column-wise: "); cm.Display(false);}// Driver Codepublic static void main(String[] args){ // Size of row or column // of square matrix int N = 4; displayRowMajor(N); displayColMajor(N);}}// This code is contributed by dharanendralv23 |
Python3
# Javascript program to convert a given# upper triangular matrix to 1D array# Create a class of Upper# Triangular Matrixclass UTMatrix : # Constructor def __init__(self, N): self.n = N; self.tot = int(N * (N + 1) / 2); self.A = [0] * (int(N * (N + 1) / 2)); # Function to display array def Display(self, row) : print(*self.A[:int(self.tot)]) # Function to generate array in # Row - Major order def setRowMajor(self, i, j, x): if (i <= j) : index = (self.n * (i - 1) - (((i - 2) * (i - 1)) / 2)) + (j - i); self.A[int(index)] = x; # Function to generate array in # Column - Major order def setColMajor(self, i, j, x) : if (i <= j) : index = int((j * (j - 1)) / 2) + i - 1; self.A[index] = x; # Function to return size of array def getN(self): return n; # Function to generate and# display array in Row-Major Orderdef displayRowMajor(N) : rm = UTMatrix(N); # Generate array in # row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(1, 2, 2); rm.setRowMajor(1, 3, 3); rm.setRowMajor(1, 4, 4); rm.setRowMajor(2, 2, 5); rm.setRowMajor(2, 3, 6); rm.setRowMajor(2, 4, 7); rm.setRowMajor(3, 3, 8); rm.setRowMajor(3, 4, 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 = UTMatrix(N); # Generate array in # column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(1, 2, 2); cm.setColMajor(1, 3, 3); cm.setColMajor(1, 4, 4); cm.setColMajor(2, 2, 5); cm.setColMajor(2, 3, 6); cm.setColMajor(2, 4, 7); cm.setColMajor(3, 3, 8); cm.setColMajor(3, 4, 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;displayRowMajor(N);displayColMajor(N);# This code is contributed by phasing17 |
C#
// C# program to convert a given// upper triangular matrix to 1D arrayusing System;// Create a class of Upper// Triangular Matrixpublic class UTMatrix{ // Size of Matrix public int n; public int[] A; // Stores count of // non-zero elements public int tot; // Constructor public UTMatrix(int N) { this.n = N; tot = N * (N + 1) / 2; A = new int[N * (N + 1) / 2]; } // Function to display array public void Display(bool row) { for(int i = 0; i < tot; i++) { Console.Write(A[i] + " "); } Console.WriteLine(); } // Function to generate array in // Row - Major order public void setRowMajor(int i, int j, int x) { if (i <= j) { int index = (n * (i - 1) - (((i - 2) * (i - 1)) / 2)) + (j - i); A[index] = x; } } // Function to generate array in // Column - Major order public void setColMajor(int i, int j, int x) { if (i <= j) { int index = ((j * (j - 1)) / 2) + i - 1; A[index] = x; } } // Function to return size of array public int getN() { return n; }}class GFG{ // Function to generate and // display array in Row-Major Order static void displayRowMajor(int N) { UTMatrix rm = new UTMatrix(N); // Generate array in // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(1, 2, 2); rm.setRowMajor(1, 3, 3); rm.setRowMajor(1, 4, 4); rm.setRowMajor(2, 2, 5); rm.setRowMajor(2, 3, 6); rm.setRowMajor(2, 4, 7); rm.setRowMajor(3, 3, 8); rm.setRowMajor(3, 4, 9); rm.setRowMajor(4, 4, 10); // Display array elements in // row-major order Console.Write("Row-Wise: "); rm.Display(false); } // Function to generate and display // array in Column-Major Order static void displayColMajor(int N) { UTMatrix cm = new UTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(1, 2, 2); cm.setColMajor(1, 3, 3); cm.setColMajor(1, 4, 4); cm.setColMajor(2, 2, 5); cm.setColMajor(2, 3, 6); cm.setColMajor(2, 4, 7); cm.setColMajor(3, 3, 8); cm.setColMajor(3, 4, 9); cm.setColMajor(4, 4, 10); // Display array elements in // column-major form Console.Write("Column-wise: "); cm.Display(false); } // Driver Code public static void Main(string[] args) { // Size of row or column // of square matrix int N = 4; displayRowMajor(N); displayColMajor(N); }}// This code is contributed by phasing17 |
Javascript
<script>// Javascript program to convert a given// upper triangular matrix to 1D array// Create a class of Upper// Triangular Matrixclass UTMatrix { // Constructor constructor(N) { this.n = N; this.tot = Math.floor(N * (N + 1) / 2); this.A = new Array(Math.floor(N * (N + 1) / 2)); } // Function to display array Display(row) { for (let i = 0; i < this.tot; i++) { document.write(this.A[i] + " "); } document.write("<br>"); } // Function to generate array in // Row - Major order setRowMajor(i, j, x) { if (i <= j) { let index = (this.n * (i - 1) - (((i - 2) * (i - 1)) / 2)) + (j - i); this.A[index] = x; } } // Function to generate array in // Column - Major order setColMajor(i, j, x) { if (i <= j) { let index = Math.floor((j * (j - 1)) / 2) + i - 1; this.A[index] = x; } } // Function to return size of array getN() { return n; }}// Function to generate and// display array in Row-Major Orderfunction displayRowMajor(N) { let rm = new UTMatrix(N); // Generate array in // row-major form rm.setRowMajor(1, 1, 1); rm.setRowMajor(1, 2, 2); rm.setRowMajor(1, 3, 3); rm.setRowMajor(1, 4, 4); rm.setRowMajor(2, 2, 5); rm.setRowMajor(2, 3, 6); rm.setRowMajor(2, 4, 7); rm.setRowMajor(3, 3, 8); rm.setRowMajor(3, 4, 9); rm.setRowMajor(4, 4, 10); // Display array elements in // row-major order document.write("Row-Wise: "); rm.Display(false);}// Function to generate and display// array in Column-Major Orderfunction displayColMajor(N) { let cm = new UTMatrix(N); // Generate array in // column-major form cm.setColMajor(1, 1, 1); cm.setColMajor(1, 2, 2); cm.setColMajor(1, 3, 3); cm.setColMajor(1, 4, 4); cm.setColMajor(2, 2, 5); cm.setColMajor(2, 3, 6); cm.setColMajor(2, 4, 7); cm.setColMajor(3, 3, 8); cm.setColMajor(3, 4, 9); cm.setColMajor(4, 4, 10); // Display array elements in // column-major form document.write("Column-wise: "); cm.Display(false);}// Driver Code// Size of row or column// of square matrixlet N = 4;displayRowMajor(N);displayColMajor(N);// This code is contributed by Saurabh Jaiswal</script> |
Output:
Row-Wise: 1 2 3 4 5 6 7 8 9 10 Column-wise: 1 2 5 3 6 8 4 7 9 10
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
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!
