Solution Approach
In this approach, we count the frequency of all the elements. The frequency of elements can be stored inside a hash table or dictionary. Once the counting is complete, print all the elements with one frequency. The algorithm is as follows:
Step 1: Create a new hash table or dictionary.
Step 2: Iterate over the matrix.
Step 3: If the current element of the matrix is present in the hash table, increase its value.
Step 4: If the element is not present in the hash table, initialize it with a value of one.
Step 5: Once the traversing over the matrix is complete, print all the elements having a frequency of one in the hash table.
Step 6: If there are no such elements, print -1.
C++ Code
// Cpp program to find unique elements in a matrix
#include<bits/stdc++.h>
using namespace std;
// Function to find the unique elements in a matrix
void findUniqueElements(vector<vector<int>> & matrix, int rows, int cols){
// Initialising an unordered map to store the frequency
unordered_map<int,int> frequencyTable;
bool noUniqueElements = true; // Variable to store if there are any unique elements in the matrix
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
frequencyTable[matrix[i][j]]++; // Increase the counter
}
}
// Iterate over the frequency Table and
// print all the elements having a frequency of one.
for(auto it: frequencyTable){
int key = it.first;
int value = it.second;
if(value == 1){
noUniqueElements = false; // set noUniqueElements to false
// print all the elements with frequency one
cout<<key<<" ";
}
}
// print -1 if there are no unique elements
if(noUniqueElements){
cout<<-1;
}
// New line
cout<<endl;
}
// Main function to run the program
int main(){
// Input Matrix
vector<vector<int>> matrix = {{ 1, 2, 3, 4 },
{5, 6, 7, 8},
{1, 2, 3 ,4},
{13, 8, 3, 16} };
int rows = 4; // Total number of rows in the matrix
int cols = 4; // Total numberof cols in the matrix
// Calling findUniqueElements function to
// find all the unique elements in the matrix.
findUniqueElements(matrix, rows, cols);
return 0;
}
Python Code
# Python program to find unique elements in a matrix
# Function to find the unique elements in a matrix
def findUniqueElements(matrix, rows, cols):
# Initialising a dictionary p to store the frequency
frequencyTable = dict()
noUniqueElements = True # Variable to store if there are any unique elements in the matrix
for i in range(rows):
for j in range(cols):
key = matrix[i][j]
if key in frequencyTable:
frequencyTable[key]+=1 # Increase the counter
else:
frequencyTable[key] =1
# Iterate over the frequency Table and
# print all the elements having frequency of one.
for key in frequencyTable:
value = frequencyTable[key]
if(value == 1):
noUniqueElements = False # set noUniqueElements to false
# print all the elements with frequency one
print(key, end= " ")
# print -1 if there are no unique elements
if(noUniqueElements):
print(-1)
# New line
print()
# Main function to run the program
if __name__ == "__main__":
# Input Matrix
matrix = [[ 1, 2, 3, 4 ],[5, 6, 7, 8],[1, 2, 3 ,4],[13, 8, 3, 16]]
rows = 4 # Total number of rows in the matrix
cols = 4 # Total number of cols in the matrix
# Calling findUniqueElements function to
# find all the unique elements in the matrix.
findUniqueElements(matrix, rows, cols)
Java Code
// Java program to compute scalar Multiplication of a matrix
import java.util.*;
class main
{
// Function to find the unique elements in a matrix
static void findUniqueElements(int [][]matrix, int rows, int cols){
// Initialising a Hashmap to store the frequency
HashMap<Integer,Integer> frequencyTable = new HashMap<>();
boolean noUniqueElements = true; // Variable to store if there are any unique elements in the matrix
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
Integer key = matrix[i][j];
if(frequencyTable.containsKey(key)){
// If the key is present in the table, increment the value by one.
Integer value = frequencyTable.get(key);
frequencyTable.put(key,value+1);
}
else{
// else put a new entry for key with value one
frequencyTable.put(key,1);
}
}
}
// Iterate over the frequency Table and
// print all the elements having a frequency of one.
for (Map.Entry mapElement : frequencyTable.entrySet()) {
// Fetch the key
Integer key = (Integer)mapElement.getKey();
// Value corresponding to the key
int value = ((int)mapElement.getValue());
// if value (i.e, frequency) is one, print the key and set noUniqueElements to false
if(value == 1){
noUniqueElements = false;
System.out.print(key + " ");
}
}
// print -1 if there are no unique elements
if(noUniqueElements){
System.out.print(-1);
}
// New line
System.out.println();
}
// Main function to run the program
public static void main(String args[]){
// Input Matrix
int matrix [][] = {{ 1, 2, 3, 4 },
{5, 6, 7, 8},
{1, 2, 3 ,4},
{13, 8, 3, 16} };
int rows = 4; // Total number of rows in the matrix
int cols = 4; // Total number of cols in the matrix
// Calling findUniqueElements function to
// find all the unique elements in the matrix.
findUniqueElements(matrix, rows, cols);
}
}
Output:
7 6 13 16 5
Time Complexity: O(n^2), where n = Max(number of rows, number of cols)
Space Complexity: O(n^2), where n= Max(number of rows, number of cols)
Check out this problem - Matrix Median
Frequently Asked Questions
Is it possible to keep the order of elements in the way they arrive while using an unordered map?
No, an unordered map does not guarantee the order of the elements. It stores the elements in random order. If you wish to keep the elements in order, you can use a map instead of an unordered map.
Why do the above codes give different outputs when run for different languages?
The output order might be different, but the elements would be the same. It is because different languages store the keys in different orders. Like - the unordered map in CPP stores the key in random order. Therefore, the order of the output may be different for different languages.
Can this problem be solved with a time complexity less than O(n^2)?
To find the unique elements in a matrix, you need to iterate over the matrix once, which can not be done in time less than O(n^2). Hence the time complexity can not be less than O(n^2).
Conclusion
In this article, we have extensively discussed the problem of finding unique elements in a matrix. We hope that this blog has helped you enhance your knowledge, to learn more, check out our article on Scalar Multiplication of a matrix.
And also, check out the awesome content on the Coding Ninjas Website,
Android Development, Coding Ninjas Studio Problems, Coding Ninjas Studio Interview Bundle, Coding Ninjas Studio Interview Experiences, Coding Ninjas Courses, Coding Ninjas Studio Contests, and Coding Ninjas Studio Test Series. Do upvote our blog to help other ninjas grow. Happy Coding!
235+ registered 
