Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Solution Approach
3.1.
C++ Code
3.2.
Python Code
3.3.
Java Code
4.
Frequently Asked Questions
4.1.
Is it possible to keep the order of elements in the way they arrive while using an unordered map?
4.2.
Why do the above codes give different outputs when run for different languages?
4.3.
Can this problem be solved with a time complexity less than O(n^2)?
5.
Conclusion 
Last Updated: Mar 27, 2024
Easy

Unique elements in a Matrix

Author Pradeep Kumar
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will look at the problem of finding unique elements in a matrix. Unique elements are the elements that occur only once in the whole matrix. For the implementation, Vectors of C++ are used; if you are not familiar with vectors, you can check out this article.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

Given a matrix, find out all the unique elements in the matrix. In case there are no unique elements, print -1.

Examples:

Input: 3 6
           6 4        
Output: 3 4
Explanation: 3 and 4 appears once, while 6 appear twice in the matrix.
 
Input: 2 2 8 4
           6 6 4 8
Output:  -1
Explanation: The frequency of all the elements is two. Hence, there are no unique elements.       
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

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 DevelopmentCoding Ninjas Studio ProblemsCoding Ninjas Studio Interview BundleCoding Ninjas Studio Interview ExperiencesCoding Ninjas CoursesCoding Ninjas Studio Contests, and Coding Ninjas Studio Test SeriesDo upvote our blog to help other ninjas grow. Happy Coding!

Previous article
Diagonally Dominant Matrix
Next article
Scalar Multiplication of a matrix
Live masterclass