Skip to main content

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:

  1. Initialize a linked list to store the distinct elements common to all rows.
  2. Add all the elements from the first row of the matrix into the linked list.
  3. For each subsequent row, remove the elements from the linked list that do not exist in the current row.
  4. After iterating through all rows, the linked list will contain the distinct elements common to all rows.
  5. 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

  1. 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.
  2. A linked list, 'list_node', is created to store the distinct elements common to all rows.
  3. The elements from the first row of the matrix are added to the linked list using the 'add_node' function of the 'LinkedList' class.
  4. The function uses three variables, 'auxiliary', 'temp', and 'back', for linked list operations.
  5. It starts from the second row (i=1) and iterates through each row of the matrix.
  6. For each row, it removes the elements from the linked list that do not exist in the current row using the 'find_element' function.
  7. The 'find_element' function checks if an element exists in the given row of the matrix or not.
  8. After removing the elements, the 'auxiliary' variable is moved to the next node in the linked list to process the next row.
  9. The function continues this process for all rows of the matrix.
  10. 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.





Comment

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