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.
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:
Map the first row's element in a hash table. Make this as a hash.
Starting the row from 2 till the last n, do the following.
Create a temporary hash table by mapping the current row's elements. It is temp in our example.
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.
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:
Insert every element from the first row into the map. In our example, it is res.
Now we determine whether or not each row contains the elements present on the map.
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.
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);
}
}
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.
8+ registered 