Find distinct elements common to all rows of a matrix

Difficulty Level Hard
Frequently asked in BlackRock Expedia JP Morgan Qualcomm Snapdeal Yatra Zoho
Hashing Matrix SortingViews 3166

Problem Statement

We are given a matrix of all the integers. The problem “Find distinct elements common to all rows of a matrix” asks to find out all the possible distinct elements but common in each of the rows present in a matrix.

Example

arr[]={ {11, 12, 3, 10},

{11, 5, 8, 3},

{7, 11, 3, 10},

{9, 10, 11, 3}}
3 11

Explanation: 3 and 11 are the two numbers that are distinct and also common in each of the rows in a given matrix.

Algorithm to find distinct elements common to all rows of a matrix

1. Declare a Set “SETValue”.
2. Add all the values of the first row of a matrix into the “SETValue”.
3. Traverse the matrix from the second row of a given matrix.
  1. Declare a new set let’s say “temp”, every time for each row of a matrix.
    1. Add all the values of that particular row in “temp” Set.
  2. Iterate over the set “SETValue” in which we stored our first row values.
    1. Check if temp contains any of the value of SETValue.
      1. If it contains, then removes that value from the SETValue.
  3. If SETValue size is equal to 0, then break the loop.
4. Traverse SETValue and print all the values in it.

Explanation

Given a matrix of integers. Our task is to find out all the possible values of a matrix that are distinct to each other. And also common in each of the rows in a matrix. We will be using the Set Data Structure in solving this question. This Set Data Structure helps in removing or not accepting the copied elements. We will be traversing the matrix from the second row of the matrix. Because the first row we will be already assigned to a Set.

We will declare a Set first called SETValue and add all the values of a matrix’s first row into the set. This is just because we have to check all the elements that they should be common in all of the rows. So we can use the first row that will be assigned to a Set as a reference.

We will be traversing the matrix now from the second-row elements because we have already covered the first row and now from the second row we will be taking a new Set Data structure, in fact, we will be taking new Data Structure for each new row of a given matrix in the traversal. Because we have to store those particular row elements into the new Set called “temp”. Then we are going to check if any of the value of SETValue is present in temp if present then we are going to remove that element. Also, we have put one condition there to check the null pointer exception value. If the size of the SETValue set will become 0, then it will break the loop and there will be no runtime error.

As we are removing the elements from SETValue, we have an output value in there after the traversal, so we will be printing those values.

Find distinct elements common to all rows of a matrix

Code

C++ code to find distinct elements common to all rows of a matrix

#include<unordered_set>
#include<iostream>

using namespace std;

const int MAX = 100;

void getDistinctCommonElements (int mat[][MAX], int n)
{
    unordered_set<int> SETValue;

    for (int i=0; i<n; i++)
        SETValue.insert(mat[0][i]);

    for (int i=1; i<n; i++)
    {
        unordered_set<int> temp;

        for (int j=0; j<n; j++)
            temp.insert(mat[i][j]);

        unordered_set<int>:: iterator itr;

        for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)

            if (temp.find(*itr) == temp.end())
                SETValue.erase(*itr);

        if (SETValue.size() == 0)
            break;
    }
    unordered_set<int>:: iterator itr;
    for (itr=SETValue.begin(); itr!=SETValue.end(); itr++)
        cout << *itr << " ";
}
int main()
{
    int mat[][MAX] =  { {11, 12, 3, 10},
        {11, 5, 8, 3},
        {7, 11, 3, 1},
        {9, 0, 11, 3}
    };
    int n = 4;
    getDistinctCommonElements (mat, n);
    return 0;
}

3 11

Java code to find distinct elements common to all rows of a matrix

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Collection;

class DistinctCommonElements
{
    public static void getDistinctCommonElements(int mat[][], int n)
    {
        Collection<Integer> removeElements = new LinkedList<Integer>();
        HashSet<Integer> SETValue=new HashSet<>();

        for (int i=0; i<n; i++)
            SETValue.add(mat[0][i]);

        for (int i=1; i<n; i++)
        {
            HashSet<Integer> temp= new HashSet<Integer>();
            for (int j=0; j<n; j++)
                temp.add(mat[i][j]);

            for(Integer element : SETValue)
                if(!(temp.contains(element)))
                    removeElements.add(element);

            SETValue.removeAll(removeElements);

            if (SETValue.size() == 0)
                break;
        }
        Iterator<Integer> itr=SETValue.iterator();
        while(itr.hasNext())
            System.out.print(itr.next()+" ");
    }
    public static void main(String [] args)
    {
        int mat[][] = { {11, 12, 3, 10},
            {11, 5, 8, 3},
            {7, 11, 3, 10},
            {9, 10, 11, 3}
        };
        int n = 4;
        getDistinctCommonElements (mat, n);
    }
}

3 11

Complexity Analysis

Time Complexity

Here we have been using two nested loops and using unordered_set/HashSet gave us polynomial time complexity. O(n2) where “n” is the size of the matrix.

Space Complexity

O(n) where “n” is the size of the matrix, for storing the input and storing elements in HashSet.

Translate »