Convert given upper triangular Matrix to 1D Array

0 0 9 minutes read

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 Matrix
class 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 order
void 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 order
void 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 elements
void 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 Order
void 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 Order
void 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 Code
int 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 Matrix
class UTMatrix{
     
// Size of Matrix
private int n;
 
private int[] A = new int[n];
 
// Stores count of
// non-zero elements
private 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
void 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 order
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
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
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
    System.out.print("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
    System.out.print("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 dharanendralv23

Python3

# Javascript program to convert a given
# upper triangular matrix to 1D array
 
# Create a class of Upper
# Triangular Matrix
class 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 Order
def 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 Order
def 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 matrix
N = 4;
 
displayRowMajor(N);
displayColMajor(N);
 
# This code is contributed by phasing17

C#

// C# program to convert a given
// upper triangular matrix to 1D array
using System;
 
// Create a class of Upper
// Triangular Matrix
public 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 Matrix
class 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 Order
function 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 Order
function 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 matrix
let 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 zambiatek!