Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
2.1.1.
Example 1
2.1.2.
Example 2
3.
Approaches
3.1.
Method 1
3.2.
Method 2
3.2.1.
C++ Code
3.2.2.
Java Code
3.3.
Method 3
3.3.1.
C++ Code
3.3.2.
Java Code
3.4.
Method 4
3.4.1.
C++ Code
3.4.2.
Java Code
4.
Frequently Asked Questions
4.1.
How to traverse a matrix?
4.2.
Can the size of an array be changed while it is running?
4.3.
Is there a distinction between int[] a and int a[]?
5.
Conclusion
Last Updated: Mar 27, 2024

Finding the distinct elements common to all rows of the matrix

Author Gurleen Kaur
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will learn to solve a multi-dimensional array problem to find distinct elements common to all rows of a matrix and its time and space complexities. This blog covers a matrix problem. Matrices are one of the most popular and commonly asked data structures in programming contests and technical interviews. There are many standard matrix problems and techniques.

This article will go through the entire problem statement, example application, algorithm, and complexities.

Problem Statement

An n*n matrix is given, the aim is to find the distinct elements common to all rows of a matrix where we need to see all the distinct elements, but they are common in every row present in the matrix. Check out the example to understand.

Sample Examples

Example 1

Input : mat[ ][ ] = {  {2, 1, 4, 3},
                                 {1, 3, 6, 3},  
                                 {2, 1, 2, 3},  
                                 {1, 2, 5, 3} }
Output : 1 3
Explanation: We see that 1 and 3 are distinct elements in every row of the above matrix, hence the output.

Example 2

Input : mat[ ][ ] = {  {10, 1, 14, 2, 13} ,
                                 {14, 3, 1, 2, 22},  
                                 {14, 1, 14, 2, 10},  
                                 {14, 22, 3, 2, 1},
                                 {1, 18, 2, 21, 14} }
Output : 1 2 14 
Explanation: We see all 1, 2, and 14 are distinct elements but are present in every row of the above matrix, hence the output.

 

Also see,  Rabin Karp Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approaches

Now, we will look at different methods to solve this problem:

Method 1

Three nested loops are used. Verify that each row after the first contains an element from the first row. Time Complexity is O(n3). To accommodate the duplicate elements, additional space could be needed.

Method 2

Sort the matrix's rows in ascending order. Apply a modified strategy to the problem of finding common elements among three sorted arrays after that. The implementation of the same is provided below.

C++ Code

#include <bits/stdc++.h> 
using namespace std; 
const int MAX = 100; 
// the sortingRows function 
void sortingRows(int arr[ ][MAX], int n) 
{ 
    for (int i=0; i<n; i++) 
        sort(arr[i], arr[i] + n); 
} 
  
// finding the common elements 
void printSameElements(int arr[ ][MAX], int n) 
{ 
    sortingRows(arr, n);
    // store the index of the column, the index from where element is searched in every row
    int sample = 0; 
    int index[n]; 
    int length=sizeof(index);
    memset(index, 0, sizeof(length));
    for (; index[0]<n; index[0]++) 
    { 
        int temp = arr[0][index[0]]; 
        bool current = true; 
        // In every upcoming row, this ‘temp’ is searched
        for (int i=1; i<n; i++) 
        { 
            // traverse the array until following condition is not met
            while (index[i] < n && arr[i][index[i]] <= temp) 
          {
                index[i]++; 
           }
            if (arr[i][index[i]-1] != temp) 
                current = false; 
          // you are at the end of the array
              if (index[i] == n) 
            { 
                sample = 1; 
                break; 
            } 
        } 
  
        // if the 'temp' is common to all the rows 
        if (current) 
            cout << temp << " ";
    // no more common elements left since one of the row is completely traversed
        if (sample == 1) 
            break; 
    } 
} 
  
// Driver program
int main() 
{ 
    // example used here
    int mat[][MAX] = {  {2, 1, 4, 3} ,
                                 {1, 3, 6, 3} ,  
                                 {2, 1, 2, 3} ,  
                                 {1, 2, 5, 3}  };
  
    int n = 4; 
    printSameElements(mat, n); 
    return 0; 
} 

Output:

1 3

Java Code

import java.util.*;   
class codingninjas { 
      // function sortingRows
    public static void sortingRows(int arr[][], int n) 
    { 
        for (int i=0; i<n; i++) 
            Arrays.sort(arr[i]); 
    } 
       
   // finding all the common elements 
    public static void printSameElements(int arr[][], int n) 
    { 
        //function call
        sortingRows(arr, n); 
        // store the index of the column, the index from where element is searched in every row
        int sample = 0; 
        int index[] = new int[n];
        for (; index[0]<n; index[0]++) 
        { 
            int temp = arr[0][index[0]]; 
            boolean current = true; 
            //Now, 'temp' is being searched in every upcoming row
            for (int i=1; i<n; i++) 
            { 
            //traverse until conditions present in while loop are true
                while (index[i] < n &&  arr[i][index[i]] <= temp) {
                    index[i]++; 
               }
                if (arr[i][index[i]-1] != temp) 
                    current = false; 
                // you are at the end of the array
                if (index[i] == n) 
                { 
                    sample = 1; 
                    break; 
                } 
            }
            if (current) 
               System.out.print(temp+" "); 
            // no more common elements left since one of the row is completely traversed
            if (sample == 1) 
                break; 
        } 
    } 
    // Driver code
    public static void main(String[] args)  
    { 
        // example used
        int arr[][] =  {  {2, 1, 4, 3} ,
                                 {1, 3, 6, 3} ,  
                                 {2, 1, 2, 3} ,  
                                 {1, 2, 5, 3}  }; 
           
            int n = 4; 
            printSameElements(arr, n); 
    } 
  } 

Output:

1 3

Time Complexity: O(n2logn)

Space Complexity: O(n)

Method 3

The concept of hashing is used in this method. The following steps should be followed:

  1. Map the first row's element in a hash table. Make this as a hash.
  2. Starting the row from 2 till the last n, do the following.
  3. Create a temporary hash table by mapping the current row's elements. It is temp in our example.
  4. Check whether the hash's elements are present in this ‘temp’ by iterating through the hash's elements. Remove those elements from the hash if they are absent.
  5. The components still in the hash are the necessary common elements once all the rows have been processed.

C++ Code

#include<bits/stdc++.h>
using namespace std;
const int MAX = 100;
void getSameElements (int arr[][MAX], int n)
{
    unordered_set<int> Value;
    //mapping first row elements (step 1 from algorithm)
    for (int i=0; i<n; i++)
        Value.insert(arr[0][i]);
    for (int i=1; i<n; i++)
    {
        unordered_set<int> temp;
        //mapping elements to temp (step 2 and 3 from algorithm)
        for (int j=0; j<n; j++)
            temp.insert(arr[i][j]);
         // step 4 from our algorithm
        unordered_set<int>:: iterator itr;
        for (itr=Value.begin(); itr!=Value.end(); itr++)
            if (temp.find(*itr) == temp.end())
                Value.erase(*itr);


                // if size of set is 0, there are no elements
        if (Value.size() == 0)
            break;
    }
// required elements (step 5 from the algorithm)
    unordered_set<int>:: iterator itr;
    for (itr=Value.begin(); itr!=Value.end(); itr++)
        cout << *itr << " ";
}
//main program
int main()
{
    //example used
    int arr[][MAX] = {  {10, 1, 14, 2, 13} ,
                                 {14, 3, 1, 2, 22} ,  
                                 {14, 1, 14, 2, 10} ,  
                                 {14, 22, 3, 2, 1} ,
                                 {1, 18, 2, 21, 14}  };


    int n = 5;
    getSameElements (arr, n);
    return 0;
}

Output:

1 2 14

Java Code

import java.util.*;
public class CommonElements
{
    //function getCommonElements
    public static void getCommonElements(int arr[][], int n)
    {
        Collection<Integer> eraseElements = new LinkedList<Integer>();
        HashSet<Integer> Value=new HashSet<Integer>();
        //step 1 from algorithm (mapping of first row elements)
        for (int i=0; i<n; i++)
            Value.add(arr[0][i]);
        for (int i=1; i<n; i++)
        {
            HashSet<Integer> temp= new HashSet<Integer>();
           //Mapping elemments to temp (step 2 from algorithm)
            for (int j=0; j<n; j++)
                temp.add(arr[i][j]);
            // Step 3 from the algorithm
            for(Integer element : Value)
                if(!(temp.contains(element)))
                    eraseElements.add(element);
            Value.removeAll(eraseElements);
            // No common elements since size is 0
            if (Value.size() == 0)
                break;
        }
        Iterator<Integer> itr=Value.iterator();
        while(itr.hasNext())
            System.out.print(itr.next()+" ");
    }
    //Main program
    public static void main(String [] args)
    {
        //example used
        int arr[][] =  {  {10, 1, 14, 2, 13} ,
                                 {14, 3, 1, 2, 22} ,  
                                 {14, 1, 14, 2, 10} ,  
                                 {14, 22, 3, 2, 1} ,
                                 {1, 18, 2, 21, 14}  };


        int n = 5;
        getCommonElements (arr, n);
    }
}

Output:

1 2 14

Time Complexity: O(n2

Space Complexity: O(n)

Method 4

The concept of the map is used; follow the following steps:

  1. Insert every element from the first row into the map. In our example, it is res.
  2. Now we determine whether or not each row contains the elements present on the map.
  3. We increase the count of the element in the map by one if it is present in the map and is not a duplicate in the current row.
  4. We print the element if it appears (N-1) times earlier and reaches the last row while traversing.

C++ Code

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
 // Distinct_common function
void Distinct_common(int arr[][MAX], int N)
{
  unordered_map<int,int> res;
  //Put elements for first row in map and initialise them by 1 (step 1 of the algorithm)
  for (int j = 0; j < N; j++) {
    res[arr[0][j]]=1;
  }
  // Traversing of matrix from the second row (step 2 from the algorithm)
  for (int i = 1; i < N; i++) {
    for (int j = 0; j < N; j++) {
 
      // step 3 from the algorithm
      if (res[arr[i][j]] != 0 && res[arr[i][j]] == i) {
        res[arr[i][j]]= i + 1;
 
        //Step 4 from the algorithm(printing values)
        if (i == N - 1) {
          cout<<arr[i][j]<<" ";
        }
      }
    }
  }
}
 
// Main program
int main()
{
  int N=4;
  //example used
  int arr[][MAX] = { {2, 1, 4, 3},
                    {1, 2, 4, 2},
                    {4, 6, 2, 4},
                    {5, 2, 4, 3}  };
  //function call
  Distinct_common(arr, N);
  return 0;
}

Output:

2 4

Java Code

import java.util.*;
 
public class codingninjas {
  // distinct_common function
  static void distinct_common(int arr[][], int n)
  {
    Map<Integer, Integer> res = new HashMap<Integer, Integer>();
   //Put elements for first row in map and initialise them by 1 (step of the algorithm)
    for (int j = 0; j < n; j++) {
      res.put(arr[0][j], 1);
    }
   //Traversing of matrix from the second row (step 2 from the algorithm)
    for (int i = 1; i < n; i++) {
      for (int j = 0; j < n; j++) {
 
        // Step 3 of the algorithm
        if (res.get(arr[i][j]) != null && res.get(arr[i][j]) == i) {
          // Increment the count of element by 1
          res.put(arr[i][j], i + 1);
 
          // If we have reached the last row (step 4 of the algorithm)
          if (i == n - 1) {
           // printing the elements
            System.out.print(arr[i][j] + " ");
          }
        }
      }
    }
  } 
  // Main program
  public static void main(String[] args)
  {
    //example used
    int arr[][] = { {2, 1, 4, 3},
                    {1, 2, 4, 2},
                    {4, 6, 2, 4},
                    {5, 2, 4, 3}  };
    int n = 4;
   //function call
    distinct_common(arr, n);
  }
}

Output:

2 4

Time Complexity: O(n2

Space Complexity: O(n)

Check out this problem - Find Duplicate In Array

Frequently Asked Questions

How to traverse a matrix?

There are two popular ways to traverse a matrix: row-major-order and column-major-order. A matrix is considered to be in row-major order when it can be accessed row by row. It is referred to as column-major order when a matrix is accessed column by column. Before moving on to the solution, you should test your method in the IDE.

Can the size of an array be changed while it is running?

The array size cannot be changed. Nevertheless, there are similar data types that permit size changes.

Is there a distinction between int[] a and int a[]?

There is no difference between the two; they both are legal statements.

Conclusion

This article extensively discusses a multi-dimensional array problem to print distinct elements common to all rows of a matrix and its time and space complexities. We hope this article has helped you with additional information about Data Structures and algorithms. And to train yourself in-depth about Multi-dimensional Arrays, check out the course on Arrays on the Coding Ninjas website. Look at the Coding Ninjas website for knowledge on Android DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blogs.

Happy Programming!

Previous article
Shifting matrix elements row-wise by k
Next article
Implementation of Deque Using A Circular Array
Live masterclass