Find the distinct elements common to all rows of a matrix
The problem is to find the distinct elements common to all rows of a given matrix. We need to collect and display the elements that are present in all rows without repetition.
Problem Statement and Example
Consider the following matrix:
1 6 0 5 2 9 3 5 4
17 0 9 3 4 1 5 2 4
0 5 3 1 6 8 2 1 4
1 5 8 9 2 4 0 2 3
1 7 8 6 1 5 0 3 3
The distinct elements common to all rows in this matrix are: 1, 0, 5, and 3.
Idea to Solve the Problem
To find the distinct elements common to all rows of the matrix, we can follow the following approach:
- Initialize a linked list to store the distinct elements common to all rows.
- Add all the elements from the first row of the matrix into the linked list.
- For each subsequent row, remove the elements from the linked list that do not exist in the current row.
- After iterating through all rows, the linked list will contain the distinct elements common to all rows.
- Display the elements present in the linked list as the output.
Pseudocode
distinct_elements(matrix):
rows = number of rows in the matrix
cols = number of columns in the matrix
// Create a linked list
list_node = new LinkedList()
// Add all elements from the first row to the linked list
for i from 0 to cols:
list_node.add_node(matrix[0][i])
// Initialize auxiliary and temp variables for linked list operations
auxiliary = list_node.head
temp = null
back = null
// Start from the second row
i = 1
while auxiliary is not null and i < rows:
temp = auxiliary
auxiliary = null
back = null
// Remove elements from the linked list that do not exist in the current row
while temp is not null:
if find_element(matrix, i, cols, temp.data) is 0:
// Delete the node from the linked list
if back is null:
list_node.head = temp.next
auxiliary = temp
temp = list_node.head
else:
auxiliary = temp
temp = temp.next
back.next = temp
auxiliary = null
else:
back = temp
temp = temp.next
// Move to the next node in the linked list
auxiliary = list_node.head
i = i + 1
// Display the distinct elements common to all rows
list_node.node_result()
Algorithm Explanation
- The 'distinct_elements' function takes the 2D matrix 'matrix' as input and initializes the number of rows 'rows' and number of columns 'cols' in the matrix.
- A linked list, 'list_node', is created to store the distinct elements common to all rows.
- The elements from the first row of the matrix are added to the linked list using the 'add_node' function of the 'LinkedList' class.
- The function uses three variables, 'auxiliary', 'temp', and 'back', for linked list operations.
- It starts from the second row (i=1) and iterates through each row of the matrix.
- For each row, it removes the elements from the linked list that do not exist in the current row using the 'find_element' function.
- The 'find_element' function checks if an element exists in the given row of the matrix or not.
- After removing the elements, the 'auxiliary' variable is moved to the next node in the linked list to process the next row.
- The function continues this process for all rows of the matrix.
- Finally, the 'node_result' function of the 'LinkedList' class is called to display the distinct elements common to all rows.
Code Solution
// C Program
// Find the distinct elements common to all rows of a matrix
#include <stdio.h>
#include <malloc.h>
//Size of Matrix
#define R 5
#define C 9
// Linked List node
struct Node
{
int data;
struct Node *next;
};
// Define LinkedList
struct LinkedList
{
struct Node *head;
};
// Create a new node of linked list
struct Node *new_node(int data)
{
// Create dynamic node of Node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("\nMemory Overflow, when creating a new Node\n");
}
else
{
node->data = data;
node->next = NULL;
}
return node;
}
// Create a new linked list
struct LinkedList *linked_list()
{
// Create dynamic list of LinkedList
struct LinkedList *new_list = (struct LinkedList *) malloc(sizeof(struct LinkedList));
if (new_list == NULL)
{
printf("\nMemory Overflow, when creating a new LinkedList\n");
}
else
{
new_list->head = NULL;
}
return new_list;
}
// Add nodes in linked list
void add_node(struct LinkedList *list_node, int data)
{
if (list_node->head == NULL)
{
list_node->head = new_node(data);
}
else
{
struct Node *temp = list_node->head;
//Find last node position
while (temp->next != NULL)
{
if (temp->data == data || temp->next->data == data)
{
//Node already exists
return;
}
temp = temp->next;
}
//Add node at last position
temp->next = new_node(data);
}
}
//Check element exists in given row
int find_element(int matrix[R][C], int row, int element)
{
for (int i = 0; i < C; ++i)
{
if (matrix[row][i] == element)
{
return 1;
}
}
return 0;
}
// Display result
void node_result(struct LinkedList *list_node)
{
struct Node *temp = list_node->head;
printf(" Distinct row elements is : ");
if (temp == NULL)
{
printf(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != NULL)
{
printf(" %d", temp->data);
//Visit to next node
temp = temp->next;
}
printf("\n");
}
}
// Collect and display the distinct elements of matrix by row wise
void distinct_elements(int matrix[R][C])
{
// Create a empty linked list
struct LinkedList *list_node = linked_list();
// Loop controlling variable
int i = 0;
//Add first row into linked list
for (i = 0; i < C; ++i)
{
add_node(list_node, matrix[0][i]);
}
//Define some useful Node variables
struct Node *auxiliary = list_node->head;
struct Node *temp = NULL;
struct Node *back = NULL;
//starting row
i = 1;
while (auxiliary != NULL && i < R)
{
temp = auxiliary;
// Reset values
auxiliary = NULL;
back = NULL;
// Check and remove linked list node which is not in matrix row
while (temp != NULL)
{
//check that whether linked list node element exists in i-th row of matrix
if (find_element(matrix, i, temp->data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == NULL)
{
// Deleting first node of this linked list
list_node->head = temp->next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node->head;
}
else
{
//When an intermediate node is removed
auxiliary = temp;
temp = temp->next;
back->next = temp;
}
// Remove node
free(auxiliary);
auxiliary = NULL;
}
else
{
back = temp;
// Visit to next node
temp = temp->next;
}
}
//Start to first node of linked list
auxiliary = list_node->head;
// next row
i++;
}
// This is print similar elements in each row of given matrix
node_result(list_node);
}
int main()
{
// Define matrix of integer elements
int matrix[R][C] = {
{
1 , 6 , 0 , 5 , 2 , 9 , 3 , 5 , 4
} ,
{
17 , 0 , 9 , 3 , 4 , 1 , 5 , 2 , 4
} ,
{
0 , 5 , 3 , 1 , 6 , 8 , 2 , 1 , 4
} ,
{
1 , 5 , 8 , 9 , 2 , 4 , 0 , 2 , 3
} ,
{
1 , 7 , 8 , 6 , 1 , 5 , 0 , 3 , 3
} ,
};
distinct_elements(matrix);
return 0;
}
Output
Distinct row elements is : 1 0 5 3
/*
Java program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
// Define LinkedList
class LinkedList
{
public Node head;
public LinkedList()
{
this.head = null;
}
// Add nodes in linked list
public void add_node(int data)
{
if (this.head == null)
{
this.head = new Node(data);
}
else
{
Node temp = this.head;
//Find last node position
while (temp.next != null)
{
if (temp.data == data || temp.next.data == data)
{
//Node already exists
return;
}
temp = temp.next;
}
//Add node at last position
temp.next = new Node(data);
}
}
// Display result
public void node_result()
{
Node temp = this.head;
System.out.print(" Distinct row elements is : ");
if (temp == null)
{
System.out.print(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != null)
{
System.out.print(" " + temp.data + "");
//Visit to next node
temp = temp.next;
}
System.out.print("\n");
}
}
}
public class MyMatrix
{
//Check element exists in given row
public int find_element(int[][] matrix, int row, int cols, int element)
{
for (int i = 0; i < cols; ++i)
{
if (matrix[row][i] == element)
{
return 1;
}
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
public void distinct_elements(int[][] matrix)
{
int rows = matrix.length;
int cols = matrix[0].length;
// Create a empty linked list
LinkedList list_node = new LinkedList();
// Loop controlling variable
int i = 0;
//Add first row into linked list
for (i = 0; i < cols; ++i)
{
list_node.add_node(matrix[0][i]);
}
//Define some useful Node variables
Node auxiliary = list_node.head;
Node temp = null;
Node back = null;
//starting row
i = 1;
while (auxiliary != null && i < rows)
{
temp = auxiliary;
// Reset values
auxiliary = null;
back = null;
// Check and remove linked list node which is not in matrix row
while (temp != null)
{
//check that whether linked list node element exists in i-th row of matrix
if (this.find_element(matrix, i, cols, temp.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == null)
{
// Deleting first node of this linked list
list_node.head = temp.next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
//When an intermediate node is removed
auxiliary = temp;
temp = temp.next;
back.next = temp;
}
// Remove node
auxiliary = null;
}
else
{
back = temp;
// Visit to next node
temp = temp.next;
}
}
//Start to first node of linked list
auxiliary = list_node.head;
// next row
i++;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
public static void main(String[] args)
{
MyMatrix mat = new MyMatrix();
// Define matrix of integer elements
int[][] matrix = {
{
1 , 6 , 0 , 5 , 2 , 9 , 3 , 5 , 4
} ,
{
17 , 0 , 9 , 3 , 4 , 1 , 5 , 2 , 4
} ,
{
0 , 5 , 3 , 1 , 6 , 8 , 2 , 1 , 4
} ,
{
1 , 5 , 8 , 9 , 2 , 4 , 0 , 2 , 3
} ,
{
1 , 7 , 8 , 6 , 1 , 5 , 0 , 3 , 3
} ,
};
mat.distinct_elements(matrix);
}
}
Output
Distinct row elements is : 1 0 5 3
// Include header file
#include <iostream>
//Size of Matrix
#define R 5
#define C 9
using namespace std;
/*
C++ program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
public: int data;
Node *next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
// Define LinkedList
class LinkedList
{
public: Node *head;
LinkedList()
{
this->head = NULL;
}
// Add nodes in linked list
void add_node(int data)
{
if (this->head == NULL)
{
this->head = new Node(data);
}
else
{
Node *temp = this->head;
// Find last node position
while (temp->next != NULL)
{
// Node already exists
if (temp->data == data || temp->next->data == data)
{
return;
}
temp = temp->next;
}
// Add node at last position
temp->next = new Node(data);
}
}
// Display result
void node_result()
{
Node *temp = this->head;
cout << " Distinct row elements is : ";
if (temp == NULL)
{
cout << " None \n";
}
else
{
// Display resultant linked list nodes
while (temp != NULL)
{
cout << " " << temp->data << "";
// Visit to next node
temp = temp->next;
}
cout << "\n";
}
}
};
class MyMatrix
{
public:
// Check element exists in given row
int find_element(int matrix[R][C], int row, int cols, int element)
{
for (int i = 0; i < cols; ++i)
{
if (matrix[row][i] == element)
{
return 1;
}
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
void distinct_elements(int matrix[R][C])
{
int rows = R;
int cols = C;
// Create a empty linked list
LinkedList list_node = LinkedList();
// Loop controlling variable
int i = 0;
// Add first row into linked list
for (i = 0; i < cols; ++i)
{
list_node.add_node(matrix[0][i]);
}
// Define some useful Node variables
Node *auxiliary = list_node.head;
Node *temp = NULL;
Node *back = NULL;
// starting row
i = 1;
while (auxiliary != NULL && i < rows)
{
// next row
temp = auxiliary;
// Reset values
auxiliary = NULL;
back = NULL;
// Check and remove linked list node which is not in matrix row
while (temp != NULL)
{
// check that whether linked list node element exists in i-th row of matrix
if (this->find_element(matrix, i, cols, temp->data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == NULL)
{
// Deleting first node of this linked list
list_node.head = temp->next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
auxiliary = temp;
temp = temp->next;
back->next = temp;
}
// Remove node
auxiliary = NULL;
}
else
{
back = temp;
// Visit to next node
temp = temp->next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i++;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
};
int main()
{
MyMatrix mat = MyMatrix();
// Define matrix of integer elements
int matrix[R][C] = {
{
1 , 6 , 0 , 5 , 2 , 9 , 3 , 5 , 4
} , {
17 , 0 , 9 , 3 , 4 , 1 , 5 , 2 , 4
} , {
0 , 5 , 3 , 1 , 6 , 8 , 2 , 1 , 4
} , {
1 , 5 , 8 , 9 , 2 , 4 , 0 , 2 , 3
} , {
1 , 7 , 8 , 6 , 1 , 5 , 0 , 3 , 3
} };
mat.distinct_elements(matrix);
return 0;
}
Output
Distinct row elements is : 1 0 5 3
// Include namespace system
using System;
/*
C# program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
public class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
// Define LinkedList
public class LinkedList
{
public Node head;
public LinkedList()
{
this.head = null;
}
// Add nodes in linked list
public void add_node(int data)
{
if (this.head == null)
{
this.head = new Node(data);
}
else
{
Node temp = this.head;
// Find last node position
while (temp.next != null)
{
// Node already exists
if (temp.data == data || temp.next.data == data)
{
return;
}
temp = temp.next;
}
// Add node at last position
temp.next = new Node(data);
}
}
// Display result
public void node_result()
{
Node temp = this.head;
Console.Write(" Distinct row elements is : ");
if (temp == null)
{
Console.Write(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != null)
{
Console.Write(" " + temp.data + "");
// Visit to next node
temp = temp.next;
}
Console.Write("\n");
}
}
}
public class MyMatrix
{
// Check element exists in given row
public int find_element(int[,] matrix, int row, int cols, int element)
{
for (int i = 0; i < cols; ++i)
{
if (matrix[row,i] == element)
{
return 1;
}
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
public void distinct_elements(int[,] matrix)
{
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
// Create a empty linked list
LinkedList list_node = new LinkedList();
// Loop controlling variable
int i = 0;
// Add first row into linked list
for (i = 0; i < cols; ++i)
{
list_node.add_node(matrix[0,i]);
}
// Define some useful Node variables
Node auxiliary = list_node.head;
Node temp = null;
Node back = null;
// starting row
i = 1;
while (auxiliary != null && i < rows)
{
// next row
temp = auxiliary;
// Reset values
auxiliary = null;
back = null;
// Check and remove linked list node which is not in matrix row
while (temp != null)
{
// check that whether linked list node element exists in i-th row of matrix
if (this.find_element(matrix, i, cols, temp.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == null)
{
// Deleting first node of this linked list
list_node.head = temp.next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
auxiliary = temp;
temp = temp.next;
back.next = temp;
}
// Remove node
auxiliary = null;
}
else
{
back = temp;
// Visit to next node
temp = temp.next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i++;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
public static void Main(String[] args)
{
MyMatrix mat = new MyMatrix();
// Define matrix of integer elements
int[,] matrix = {
{
1 , 6 , 0 , 5 , 2 , 9 , 3 , 5 , 4
} , {
17 , 0 , 9 , 3 , 4 , 1 , 5 , 2 , 4
} , {
0 , 5 , 3 , 1 , 6 , 8 , 2 , 1 , 4
} , {
1 , 5 , 8 , 9 , 2 , 4 , 0 , 2 , 3
} , {
1 , 7 , 8 , 6 , 1 , 5 , 0 , 3 , 3
} };
mat.distinct_elements(matrix);
}
}
Output
Distinct row elements is : 1 0 5 3
<?php
/*
Php program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = null;
}
}
// Define LinkedList
class LinkedList
{
public $head;
function __construct()
{
$this->head = null;
}
// Add nodes in linked list
public function add_node($data)
{
if ($this->head == null)
{
$this->head = new Node($data);
}
else
{
$temp = $this->head;
// Find last node position
while ($temp->next != null)
{
// Node already exists
if ($temp->data == $data || $temp->next->data == $data)
{
return;
}
$temp = $temp->next;
}
// Add node at last position
$temp->next = new Node($data);
}
}
// Display result
public function node_result()
{
$temp = $this->head;
echo " Distinct row elements is : ";
if ($temp == null)
{
echo " None \n";
}
else
{
// Display resultant linked list nodes
while ($temp != null)
{
echo " ". $temp->data ."";
// Visit to next node
$temp = $temp->next;
}
echo "\n";
}
}
}
class MyMatrix
{
// Check element exists in given row
public function find_element( & $matrix, $row, $cols, $element)
{
for ($i = 0; $i < $cols; ++$i)
{
if ($matrix[$row][$i] == $element)
{
return 1;
}
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
public function distinct_elements( & $matrix)
{
$rows = count($matrix);
$cols = count($matrix[0]);
// Create a empty linked list
$list_node = new LinkedList();
// Loop controlling variable
$i = 0;
// Add first row into linked list
for ($i = 0; $i < $cols; ++$i)
{
$list_node->add_node($matrix[0][$i]);
}
// Define some useful Node variables
$auxiliary = $list_node->head;
$temp = null;
$back = null;
// starting row
$i = 1;
while ($auxiliary != null && $i < $rows)
{
// next row
$temp = $auxiliary;
// Reset values
$auxiliary = null;
$back = null;
// Check and remove linked list node which is not in matrix row
while ($temp != null)
{
// check that whether linked list node element exists in i-th row of matrix
if ($this->find_element($matrix, $i, $cols, $temp->data) == 0)
{
// When the elements are not exists
// delete linked list node
if ($back == null)
{
// Deleting first node of this linked list
$list_node->head = $temp->next;
// get remove node
$auxiliary = $temp;
// change current node
$temp = $list_node->head;
}
else
{
// When an intermediate node is removed
$auxiliary = $temp;
$temp = $temp->next;
$back->next = $temp;
}
// Remove node
$auxiliary = null;
}
else
{
$back = $temp;
// Visit to next node
$temp = $temp->next;
}
}
// Start to first node of linked list
$auxiliary = $list_node->head;
$i++;
}
// This is print similar elements in each row of given matrix
$list_node->node_result();
}
}
function main()
{
$mat = new MyMatrix();
// Define matrix of integer elements
$matrix = array(array(1, 6, 0, 5, 2, 9, 3, 5, 4), array(17, 0, 9, 3, 4, 1, 5, 2, 4), array(0, 5, 3, 1, 6, 8, 2, 1, 4), array(1, 5, 8, 9, 2, 4, 0, 2, 3), array(1, 7, 8, 6, 1, 5, 0, 3, 3));
$mat->distinct_elements($matrix);
}
main();
Output
Distinct row elements is : 1 0 5 3
/*
Node Js program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Define LinkedList
class LinkedList
{
constructor()
{
this.head = null;
}
// Add nodes in linked list
add_node(data)
{
if (this.head == null)
{
this.head = new Node(data);
}
else
{
var temp = this.head;
// Find last node position
while (temp.next != null)
{
// Node already exists
if (temp.data == data || temp.next.data == data)
{
return;
}
temp = temp.next;
}
// Add node at last position
temp.next = new Node(data);
}
}
// Display result
node_result()
{
var temp = this.head;
process.stdout.write(" Distinct row elements is : ");
if (temp == null)
{
process.stdout.write(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != null)
{
process.stdout.write(" " + temp.data + "");
// Visit to next node
temp = temp.next;
}
process.stdout.write("\n");
}
}
}
class MyMatrix
{
// Check element exists in given row
find_element(matrix, row, cols, element)
{
for (var i = 0; i < cols; ++i)
{
if (matrix[row][i] == element)
{
return 1;
}
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
distinct_elements(matrix)
{
var rows = matrix.length;
var cols = matrix[0].length;
// Create a empty linked list
var list_node = new LinkedList();
// Loop controlling variable
var i = 0;
// Add first row into linked list
for (i = 0; i < cols; ++i)
{
list_node.add_node(matrix[0][i]);
}
// Define some useful Node variables
var auxiliary = list_node.head;
var temp = null;
var back = null;
// starting row
i = 1;
while (auxiliary != null && i < rows)
{
// next row
temp = auxiliary;
// Reset values
auxiliary = null;
back = null;
// Check and remove linked list node which is not in matrix row
while (temp != null)
{
// check that whether linked list node element exists in i-th row of matrix
if (this.find_element(matrix, i, cols, temp.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == null)
{
// Deleting first node of this linked list
list_node.head = temp.next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
auxiliary = temp;
temp = temp.next;
back.next = temp;
}
// Remove node
auxiliary = null;
}
else
{
back = temp;
// Visit to next node
temp = temp.next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i++;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
}
function main()
{
var mat = new MyMatrix();
// Define matrix of integer elements
var matrix = [
[1, 6, 0, 5, 2, 9, 3, 5, 4] , [17, 0, 9, 3, 4, 1, 5, 2, 4] , [0, 5, 3, 1, 6, 8, 2, 1, 4] , [1, 5, 8, 9, 2, 4, 0, 2, 3] , [1, 7, 8, 6, 1, 5, 0, 3, 3]
];
mat.distinct_elements(matrix);
}
main();
Output
Distinct row elements is : 1 0 5 3
# Python 3 program
# Find the distinct elements common to all rows of a matrix
# Linked List node
class Node :
def __init__(self, data) :
self.data = data
self.next = None
# Define LinkedList
class LinkedList :
def __init__(self) :
self.head = None
# Add nodes in linked list
def add_node(self, data) :
if (self.head == None) :
self.head = Node(data)
else :
temp = self.head
# Find last node position
while (temp.next != None) :
# Node already exists
if (temp.data == data or temp.next.data == data) :
return
temp = temp.next
# Add node at last position
temp.next = Node(data)
# Display result
def node_result(self) :
temp = self.head
print(" Distinct row elements is : ", end = "")
if (temp == None) :
print(" None \n", end = "")
else :
# Display resultant linked list nodes
while (temp != None) :
print(" ", temp.data ,"", end = "")
# Visit to next node
temp = temp.next
print("\n", end = "")
class MyMatrix :
# Check element exists in given row
def find_element(self, matrix, row, cols, element) :
i = 0
while (i < cols) :
if (matrix[row][i] == element) :
return 1
i += 1
return 0
# Collect and display the distinct elements of matrix by row wise
def distinct_elements(self, matrix) :
rows = len(matrix)
cols = len(matrix[0])
# Create a empty linked list
list_node = LinkedList()
# Loop controlling variable
i = 0
# Add first row into linked list
while (i < cols) :
list_node.add_node(matrix[0][i])
i += 1
# Define some useful Node variables
auxiliary = list_node.head
temp = None
back = None
# starting row
i = 1
while (auxiliary != None and i < rows) :
# next row
temp = auxiliary
# Reset values
auxiliary = None
back = None
# Check and remove linked list node which is not in matrix row
while (temp != None) :
# check that whether linked list node element exists in i-th row of matrix
if (self.find_element(matrix, i, cols, temp.data) == 0) :
# When the elements are not exists
# delete linked list node
if (back == None) :
# Deleting first node of this linked list
list_node.head = temp.next
# get remove node
auxiliary = temp
# change current node
temp = list_node.head
else :
# When an intermediate node is removed
auxiliary = temp
temp = temp.next
back.next = temp
# Remove node
auxiliary = None
else :
back = temp
# Visit to next node
temp = temp.next
# Start to first node of linked list
auxiliary = list_node.head
i += 1
# This is print similar elements in each row of given matrix
list_node.node_result()
def main() :
mat = MyMatrix()
# Define matrix of integer elements
matrix = [
[1, 6, 0, 5, 2, 9, 3, 5, 4] , [17, 0, 9, 3, 4, 1, 5, 2, 4] , [0, 5, 3, 1, 6, 8, 2, 1, 4] , [1, 5, 8, 9, 2, 4, 0, 2, 3] , [1, 7, 8, 6, 1, 5, 0, 3, 3]
]
mat.distinct_elements(matrix)
if __name__ == "__main__": main()
Output
Distinct row elements is : 1 0 5 3
# Ruby program
# Find the distinct elements common to all rows of a matrix
# Linked List node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
# Define LinkedList
class LinkedList
# Define the accessor and reader of class LinkedList
attr_reader :head
attr_accessor :head
def initialize()
self.head = nil
end
# Add nodes in linked list
def add_node(data)
if (self.head == nil)
self.head = Node.new(data)
else
temp = self.head
# Find last node position
while (temp.next != nil)
# Node already exists
if (temp.data == data || temp.next.data == data)
return
end
temp = temp.next
end
# Add node at last position
temp.next = Node.new(data)
end
end
# Display result
def node_result()
temp = self.head
print(" Distinct row elements is : ")
if (temp == nil)
print(" None \n")
else
# Display resultant linked list nodes
while (temp != nil)
print(" ", temp.data ,"")
# Visit to next node
temp = temp.next
end
print("\n")
end
end
end
class MyMatrix
# Check element exists in given row
def find_element(matrix, row, cols, element)
i = 0
while (i < cols)
if (matrix[row][i] == element)
return 1
end
i += 1
end
return 0
end
# Collect and display the distinct elements of matrix by row wise
def distinct_elements(matrix)
rows = matrix.length
cols = matrix[0].length
# Create a empty linked list
list_node = LinkedList.new()
# Loop controlling variable
i = 0
# Add first row into linked list
while (i < cols)
list_node.add_node(matrix[0][i])
i += 1
end
# Define some useful Node variables
auxiliary = list_node.head
temp = nil
back = nil
# starting row
i = 1
while (auxiliary != nil && i < rows)
# next row
temp = auxiliary
# Reset values
auxiliary = nil
back = nil
# Check and remove linked list node which is not in matrix row
while (temp != nil)
# check that whether linked list node element exists in i-th row of matrix
if (self.find_element(matrix, i, cols, temp.data) == 0)
# When the elements are not exists
# delete linked list node
if (back == nil)
# Deleting first node of this linked list
list_node.head = temp.next
# get remove node
auxiliary = temp
# change current node
temp = list_node.head
else
# When an intermediate node is removed
auxiliary = temp
temp = temp.next
back.next = temp
end
# Remove node
auxiliary = nil
else
back = temp
# Visit to next node
temp = temp.next
end
end
# Start to first node of linked list
auxiliary = list_node.head
i += 1
end
# This is print similar elements in each row of given matrix
list_node.node_result()
end
end
def main()
mat = MyMatrix.new()
# Define matrix of integer elements
matrix = [
[1, 6, 0, 5, 2, 9, 3, 5, 4] , [17, 0, 9, 3, 4, 1, 5, 2, 4] , [0, 5, 3, 1, 6, 8, 2, 1, 4] , [1, 5, 8, 9, 2, 4, 0, 2, 3] , [1, 7, 8, 6, 1, 5, 0, 3, 3]
]
mat.distinct_elements(matrix)
end
main()
Output
Distinct row elements is : 1 0 5 3
/*
Scala program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node(var data: Int , var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
// Define LinkedList
class LinkedList(var head: Node)
{
def this()
{
this(null);
}
// Add nodes in linked list
def add_node(data: Int): Unit = {
if (this.head == null)
{
this.head = new Node(data);
}
else
{
var temp: Node = this.head;
// Find last node position
while (temp.next != null)
{
// Node already exists
if (temp.data == data || temp.next.data == data)
{
return;
}
temp = temp.next;
}
// Add node at last position
temp.next = new Node(data);
}
}
// Display result
def node_result(): Unit = {
var temp: Node = this.head;
print(" Distinct row elements is : ");
if (temp == null)
{
print(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != null)
{
print(" " + temp.data + "");
// Visit to next node
temp = temp.next;
}
print("\n");
}
}
}
class MyMatrix
{
// Check element exists in given row
def find_element(matrix: Array[Array[Int]], row: Int, cols: Int, element: Int): Int = {
var i: Int = 0;
while (i < cols)
{
if (matrix(row)(i) == element)
{
return 1;
}
i += 1;
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
def distinct_elements(matrix: Array[Array[Int]]): Unit = {
var rows: Int = matrix.length;
var cols: Int = matrix(0).length;
// Create a empty linked list
var list_node: LinkedList = new LinkedList();
// Loop controlling variable
var i: Int = 0;
// Add first row into linked list
while (i < cols)
{
list_node.add_node(matrix(0)(i));
i += 1;
}
// Define some useful Node variables
var auxiliary: Node = list_node.head;
var temp: Node = null;
var back: Node = null;
// starting row
i = 1;
while (auxiliary != null && i < rows)
{
// next row
temp = auxiliary;
// Reset values
auxiliary = null;
back = null;
// Check and remove linked list node which is not in matrix row
while (temp != null)
{
// check that whether linked list node element exists in i-th row of matrix
if (this.find_element(matrix, i, cols, temp.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == null)
{
// Deleting first node of this linked list
list_node.head = temp.next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
auxiliary = temp;
temp = temp.next;
back.next = temp;
}
// Remove node
auxiliary = null;
}
else
{
back = temp;
// Visit to next node
temp = temp.next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i += 1;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
}
object Main
{
def main(args: Array[String]): Unit = {
var mat: MyMatrix = new MyMatrix();
// Define matrix of integer elements
var matrix: Array[Array[Int]] = Array(
Array(1, 6, 0, 5, 2, 9, 3, 5, 4),
Array(17, 0, 9, 3, 4, 1, 5, 2, 4),
Array(0, 5, 3, 1, 6, 8, 2, 1, 4),
Array(1, 5, 8, 9, 2, 4, 0, 2, 3),
Array(1, 7, 8, 6, 1, 5, 0, 3, 3)
);
mat.distinct_elements(matrix);
}
}
Output
Distinct row elements is : 1 0 5 3
/*
Swift 4 program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
// Define LinkedList
class LinkedList
{
var head: Node? ;
init()
{
self.head = nil;
}
// Add nodes in linked list
func add_node(_ data: Int)
{
if (self.head == nil)
{
self.head = Node(data);
}
else
{
var temp: Node? = self.head;
// Find last node position
while (temp!.next != nil)
{
// Node already exists
if (temp!.data == data || temp!.next!.data == data)
{
return;
}
temp = temp!.next;
}
// Add node at last position
temp!.next = Node(data);
}
}
// Display result
func node_result()
{
var temp: Node? = self.head;
print(" Distinct row elements is : ", terminator: "");
if (temp == nil)
{
print(" None \n", terminator: "");
}
else
{
// Display resultant linked list nodes
while (temp != nil)
{
print(" ", temp!.data ,"", terminator: "");
// Visit to next node
temp = temp!.next;
}
print("\n", terminator: "");
}
}
}
class MyMatrix
{
// Check element exists in given row
func find_element(_ matrix: [[Int]],
_ row: Int, _ cols: Int, _ element: Int)->Int
{
var i: Int = 0;
while (i < cols)
{
if (matrix[row][i] == element)
{
return 1;
}
i += 1;
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
func distinct_elements(_ matrix: [[Int]])
{
let rows: Int = matrix.count;
let cols: Int = matrix[0].count;
// Create a empty linked list
let list_node: LinkedList = LinkedList();
// Loop controlling variable
var i: Int = 0;
// Add first row into linked list
while (i < cols)
{
list_node.add_node(matrix[0][i]);
i += 1;
}
// Define some useful Node variables
var auxiliary: Node? = list_node.head;
var temp: Node? = nil;
var back: Node? = nil;
// starting row
i = 1;
while (auxiliary != nil && i < rows)
{
// next row
temp = auxiliary;
// Reset values
auxiliary = nil;
back = nil;
// Check and remove linked list node which is not in matrix row
while (temp != nil)
{
// check that whether linked list node element exists in i-th row of matrix
if (self.find_element(matrix, i, cols, temp!.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == nil)
{
// Deleting first node of this linked list
list_node.head = temp!.next;
// get remove node
auxiliary = temp;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
auxiliary = temp;
temp = temp!.next;
back!.next = temp;
}
// Remove node
auxiliary = nil;
}
else
{
back = temp;
// Visit to next node
temp = temp!.next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i += 1;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
}
func main()
{
let mat: MyMatrix = MyMatrix();
// Define matrix of integer elements
let matrix: [[Int]] = [
[1, 6, 0, 5, 2, 9, 3, 5, 4] ,
[17, 0, 9, 3, 4, 1, 5, 2, 4] ,
[0, 5, 3, 1, 6, 8, 2, 1, 4] ,
[1, 5, 8, 9, 2, 4, 0, 2, 3] ,
[1, 7, 8, 6, 1, 5, 0, 3, 3]
];
mat.distinct_elements(matrix);
}
main();
Output
Distinct row elements is : 1 0 5 3
/*
Kotlin program
Find the distinct elements common to all rows of a matrix
*/
// Linked List node
class Node
{
var data: Int;
var next: Node? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
// Define LinkedList
class LinkedList
{
var head: Node? ;
constructor()
{
this.head = null;
}
// Add nodes in linked list
fun add_node(data: Int): Unit
{
if (this.head == null)
{
this.head = Node(data);
}
else
{
var temp: Node ? = this.head;
// Find last node position
while (temp!!.next != null)
{
// Node already exists
if (temp.data == data)
{
return;
}
temp = temp.next;
}
// Node already exists
if (temp.data == data)
{
return;
}
// Add node at last position
temp.next = Node(data);
}
}
// Display result
fun node_result(): Unit
{
var temp: Node ? = this.head;
print(" Distinct row elements is : ");
if (temp == null)
{
print(" None \n");
}
else
{
// Display resultant linked list nodes
while (temp != null)
{
print(" " + temp.data + "");
// Visit to next node
temp = temp.next;
}
print("\n");
}
}
}
class MyMatrix
{
// Check element exists in given row
fun find_element(matrix: Array < Array < Int >> , row: Int, cols: Int, element: Int): Int
{
var i: Int = 0;
while (i < cols)
{
if (matrix[row][i] == element)
{
return 1;
}
i += 1;
}
return 0;
}
// Collect and display the distinct elements of matrix by row wise
fun distinct_elements(matrix: Array < Array < Int >> ): Unit
{
var rows: Int = matrix.count();
var cols: Int = matrix[0].count();
// Create a empty linked list
var list_node: LinkedList = LinkedList();
// Loop controlling variable
var i: Int = 0;
// Add first row into linked list
while (i < cols)
{
list_node.add_node(matrix[0][i]);
i += 1;
}
// Define some useful Node variables
var auxiliary: Node ? = list_node.head;
var temp: Node ? ;
var back: Node ? ;
// starting row
i = 1;
while (auxiliary != null && i < rows)
{
// next row
temp = auxiliary;
back = null;
// Check and remove linked list node which is not in matrix row
while (temp != null)
{
// check that whether linked list node element exists in i-th row of matrix
if (this.find_element(matrix, i, cols, temp.data) == 0)
{
// When the elements are not exists
// delete linked list node
if (back == null)
{
// Deleting first node of this linked list
list_node.head = temp.next;
// change current node
temp = list_node.head;
}
else
{
// When an intermediate node is removed
temp = temp.next;
back.next = temp;
}
}
else
{
back = temp;
// Visit to next node
temp = temp.next;
}
}
// Start to first node of linked list
auxiliary = list_node.head;
i += 1;
}
// This is print similar elements in each row of given matrix
list_node.node_result();
}
}
fun main(args: Array < String > ): Unit
{
var mat: MyMatrix = MyMatrix();
// Define matrix of integer elements
var matrix: Array < Array < Int >> = arrayOf(
arrayOf(1, 6, 0, 5, 2, 9, 3, 5, 4),
arrayOf(17, 0, 9, 3, 4, 1, 5, 2, 4),
arrayOf(0, 5, 3, 1, 6, 8, 2, 1, 4),
arrayOf(1, 5, 8, 9, 2, 4, 0, 2, 3),
arrayOf(1, 7, 8, 6, 1, 5, 0, 3, 3)
);
mat.distinct_elements(matrix);
}
Output
Distinct row elements is : 1 0 5 3
Output Explanation
The given Java code defines a 'MyMatrix' class that finds the distinct elements common to all rows of the matrix and displays the result. The output displays the distinct elements common to all rows of the matrix as follows:
Distinct row elements are: 1 0 5 3
Time Complexity
The time complexity of the provided solution depends on the number of elements in the matrix. Suppose the matrix has 'm' rows and 'n' columns. The time complexity for finding distinct elements common to all rows is approximately O(m * n). The primary operations are adding elements to the linked list and removing elements from the linked list, which take linear time based on the number of elements in the matrix. The overall time complexity is linear with respect to the size of the input matrix.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment