Given a matrix arr[] of size N*N containing English alphabets characters, the task is to find the frequency of all the matrix elements.
Note: Print them in the decreasing order of the frequency.
Examples:
Input: N = 2, arr[] = {{‘a’, ‘b’}, {‘a’, ‘c’}}
Output: a : 2, b : 1, c : 1
Explanation: The frequency of a is 2.
The frequency of ‘b’ is 1 and the Frequency of ‘c’ is 1.Input: N = 3, arr[] = {{‘a’, ‘a’, ‘a’}, {‘b’, ‘a’, ‘c’}, {‘d’, ‘c’, ‘a’}}
Output: a : 5, c : 2 b : 1, d : 1
Approach: The idea to solve the problem is to find the frequency of each character and store each character with their frequency. Then sort the characters based on the frequency in decreasing order.
Follow the steps mentioned below to implement the approach.
- Declare a map to store the frequency of each element in the matrix.
- Traverse over the map and store each element with their frequency in an array (say arr2).
- Sort the array in non-increasing order based on frequency.
- Traverse the arr2[] and print the elements.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the most frequent elementvector<pair<int, char> > findMostFrequent( vector<vector<char> >& arr, int n){ // Map to store the frequency // of each character unordered_map<char, int> unmap; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { unmap[arr[i][j]]++; } } // To store the frequency of character vector<pair<int, char> > arr2; for (auto i : unmap) { arr2.push_back({ i.second, i.first }); } // Sort the array sort(arr2.rbegin(), arr2.rend()); return arr2;}// Driver codeint main(){ // Size of the matrix int N = 3; // Initialize the 2D vector vector<vector<char> > arr = { { 'a', 'a', 'a' }, { 'b', 'a', 'c' }, { 'd', 'c', 'a' } }; // Function call vector<pair<int, char> > ans = findMostFrequent(arr, N); // Print the answer for (int i = 0; i < ans.size(); i++) { cout << ans[i].second << " : " << ans[i].first << endl; } return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class Pair<K, V> { private K key; private V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; }}class GFG { // Function to find the most frequent element static List<Pair<Integer, Character> > findMostFrequent(char[][] arr, int n) { // Map to store the frequency // of each character Map<Character, Integer> unmap = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { unmap.put(arr[i][j], unmap.getOrDefault(arr[i][j], 0) + 1); } } // To store the frequency of character List<Pair<Integer, Character> > arr2 = new ArrayList<>(); for (Map.Entry<Character, Integer> entry : unmap.entrySet()) { arr2.add(new Pair<>(entry.getValue(), entry.getKey())); } // Sort the array Collections.sort( arr2, new Comparator<Pair<Integer, Character> >() { @Override public int compare( Pair<Integer, Character> o1, Pair<Integer, Character> o2) { return o2.getKey().compareTo( o1.getKey()); } }); return arr2; } public static void main(String[] args) { // Size of the matrix int N = 3; // Initialize the 2D array char[][] arr = { { 'a', 'a', 'a' }, { 'b', 'a', 'c' }, { 'd', 'c', 'a' } }; // Function call List<Pair<Integer, Character> > ans = findMostFrequent(arr, N); // Print the answer for (int i = 0; i < ans.size(); i++) { System.out.println(ans.get(i).getValue() + " : " + ans.get(i).getKey()); } }}// This code is contributed by lokesh. |
Python3
# Python3 code to implement the approach# Function to find the most frequent elementdef findMostFrequent(arr, n): # Map to store the frequency # of each character unmap = {} for i in range(n): for j in range(n): if unmap.get(arr[i][j]) != None: unmap[arr[i][j]] = unmap[arr[i][j]]+1 else: unmap[arr[i][j]] = 1 # To store the frequency of character arr2 = [] for ele1, ele2 in unmap.items(): temp = [ele2, ele1] arr2.append(temp) # Sort the array arr2.sort(reverse=True) return arr2# Driver codeif __name__ == '__main__': # Size of the matrix N = 3 # Initialize the 2D array arr = [['a', 'a', 'a'], ['b', 'a', 'c'], ['d', 'c', 'a']] # Function call ans = findMostFrequent(arr, N) # Print the answer for i in range(0, len(ans)): print(ans[i][1], ":", ans[i][0])# This code is contributed by Rohit Pradhan |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ // Function to find the most frequent element static List<pair> findMostFrequent(List<List<char>> arr, int n) { // Map to store the frequency // of each character Dictionary<char, int> unmap = new Dictionary<char, int>(); for (int i = 0 ; i < n ; i++) { for (int j = 0 ; j < n ; j++) { if(!unmap.ContainsKey(arr[i][j])){ unmap.Add(arr[i][j], 0); } unmap[arr[i][j]]++; } } // To store the frequency of character List<pair> arr2 = new List<pair>(); foreach (KeyValuePair<char,int> i in unmap) { arr2.Add(new pair(i.Value, i.Key)); } // Sort the array arr2.Sort(new Comp()); return arr2; } // Driver Code public static void Main(string[] args){ // Size of the matrix int N = 3; // Initialize the 2D vector List<List<char>> arr = new List<List<char>>{ new List<char>{ 'a', 'a', 'a' }, new List<char>{ 'b', 'a', 'c' }, new List<char>{ 'd', 'c', 'a' } }; // Function call List<pair> ans = findMostFrequent(arr, N); // Print the answer for (int i = 0 ; i < ans.Count ; i++) { Console.WriteLine(ans[i].second + " : " + ans[i].first); } }}public class pair{ public int first; public char second; public pair(int first, char second){ this.first = first; this.second = second; }}class Comp : IComparer<pair>{ public int Compare(pair o2,pair o1){ if(o1.first == o2.first){ return o1.second - o2.second; } return o1.first - o2.first; }}// This code is contributed by entertain20222. |
Javascript
//JavaScript code to implement the approachclass Pair { constructor(key, value) { this.key = key; this.value = value; }}function findMostFrequent(arr, n) { // Map to store the frequency of each character const unmap = {}; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { if (!unmap[arr[i][j]]) { unmap[arr[i][j]] = 1; } else { unmap[arr[i][j]]++; } } } // To store the frequency of character const arr2 = []; for (const key in unmap) { arr2.push(new Pair(unmap[key], key)); } // Sort the array arr2.sort((a, b) => b.key - a.key); return arr2;}// Test with sample dataconst N = 3;const arr = [ ['a', 'a', 'a'], ['b', 'a', 'c'], ['d', 'c', 'a'],];const ans = findMostFrequent(arr, N);for (let i = 0; i < ans.length; i++) { console.log(`${ans[i].value} : ${ans[i].key}`);} |
Output
a : 5 c : 2 d : 1 b : 1
Time complexity: O(N2)
Auxiliary space: O(N2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
