Find frequency of each element in given 3D Array
Given a 3D array of size N*M*P consisting only of English alphabet characters, the task is to print the frequency of all the elements in increasing order. If the frequency is the same, print them in lexicographic ordering.
Examples:
Input: N = 3, M = 4, P = 5,
matrix = { { {a, b, c, d, e}, {f, g, h, i, k}, {a, c, d, e, s}, {e, g, e, s, j} },
{ {s, j, r, s, g}, {s, t, u, e, y}, {t, y, g, j, l}, {d, r, g, t, j } },
{ {e, y, r, v, n}, {q, r, y, e, w}, {k, e, u, p, q}, {z, v, a, s, d} } }
Output:
b 1
f 1
h 1
i 1
l 1
n 1
p 1
w 1
z 1
c 2
k 2
q 2
u 2
v 2
a 3
t 3
d 4
j 4
r 4
y 4
g 5
s 6
e 8Input: N = 1, M = 1, P = 3,
matrix = { { { a, b, a} } } }
Output:
a 2
b 1
- Create a hash table using map to store the frequency of all the characters in the matrix.
- The key in a map is always in sorted order.
- Traverse the matrix and increment the frequency of the character at that position.
- Push the frequencies in a vector (say v) with their respective characters.
- Sort the frequency vector v according to the frequency.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach: #include <bits/stdc++.h> using namespace std; // Function to find frequency in 3-D matrix void findFreq( int X, int Y, int Z, vector<vector<vector< char > > >& matrix) { // Initializing unordered map unordered_map< char , int > freq; for ( int i = 0; i < X; i++) { for ( int j = 0; j < Y; j++) { for ( int k = 0; k < Z; k++) { freq[(matrix[i][j][k])]++; } } } // Store the frequency in vector vector<pair< int , char > > v; for ( auto p : freq) { v.push_back({ p.second, p.first }); } // Sort the frequency vector sort(v.begin(), v.end()); for ( auto p : v) cout << p.second << " " << p.first << endl; } // Drivers code int main() { int X = 3, Y = 4, Z = 5; // Declare 3D array of characters vector<vector<vector< char > > > matrix = { { { 'a' , 'b' , 'c' , 'd' , 'e' }, { 'f' , 'g' , 'h' , 'i' , 'k' }, { 'a' , 'c' , 'd' , 'e' , 's' }, { 'e' , 'g' , 'e' , 's' , 'j' } }, { { 's' , 'j' , 'r' , 's' , 'g' }, { 's' , 't' , 'u' , 'e' , 'y' }, { 't' , 'y' , 'g' , 'j' , 'l' }, { 'd' , 'r' , 'g' , 't' , 'j' } }, { { 'e' , 'y' , 'r' , 'v' , 'n' }, { 'q' , 'r' , 'y' , 'e' , 'w' }, { 'k' , 'e' , 'u' , 'p' , 'q' }, { 'z' , 'v' , 'a' , 's' , 'd' } } }; // Function call findFreq(X, Y, Z, matrix); return 0; } |
Java
// Java implementation of the above approach import java.util.*; class GFG { // Function to find frequency in 3-D matrix static void findFreq( int X, int Y, int Z, char [][][] matrix) { // Initializing unordered map HashMap<Character, Integer> freq = new HashMap<>(); for ( int i = 0 ; i < X; i++) { for ( int j = 0 ; j < Y; j++) { for ( int k = 0 ; k < Z; k++) { if (!freq.containsKey(matrix[i][j][k])) freq.put(matrix[i][j][k], 1 ); else freq.put(matrix[i][j][k], freq.get(matrix[i][j][k]) + 1 ); } } } // Get the size of the freq hashmap // to declare a new array int size = freq.size(); // Store the frequency in 2d array v int [][] v = new int [size][ 2 ]; int index = 0 ; for (Map.Entry mapElement : freq.entrySet()) { v[index][ 0 ] = ( char )mapElement.getKey(); v[index][ 1 ] = ( int )mapElement.getValue(); index++; } // Sort the frequency array // based on the frequencies Arrays.sort(v, (a, b) -> Integer.compare(a[ 1 ], b[ 1 ])); for ( int i = 0 ; i < size; i++) { System.out.println(( char )v[i][ 0 ] + " " + v[i][ 1 ]); } } public static void main(String[] args) { // Drivers code int X = 3 , Y = 4 , Z = 5 ; // Declare 3D array of characters char [][][] matrix = { { { 'a' , 'b' , 'c' , 'd' , 'e' }, { 'f' , 'g' , 'h' , 'i' , 'k' }, { 'a' , 'c' , 'd' , 'e' , 's' }, { 'e' , 'g' , 'e' , 's' , 'j' } }, { { 's' , 'j' , 'r' , 's' , 'g' }, { 's' , 't' , 'u' , 'e' , 'y' }, { 't' , 'y' , 'g' , 'j' , 'l' }, { 'd' , 'r' , 'g' , 't' , 'j' } }, { { 'e' , 'y' , 'r' , 'v' , 'n' }, { 'q' , 'r' , 'y' , 'e' , 'w' }, { 'k' , 'e' , 'u' , 'p' , 'q' }, { 'z' , 'v' , 'a' , 's' , 'd' } } }; // Function call findFreq(X, Y, Z, matrix); } } // this code is contributed by phasing17 |
Python3
# Python3 code to implement the above approach # Function to find frequency in 3-D matrix def findFreq(X, Y, Z, matrix): # initializing the dictionary freq = dict () for i in range (X): for j in range (Y): for k in range (Z): if matrix[i][j][k] in freq: freq[(matrix[i][j][k])] + = 1 else : freq[(matrix[i][j][k])] = 1 # store the frequency in v v = [] for p in freq: v.append([freq[p], p]) # sort the frequency vector v.sort() for p in v: print (p[ 1 ], p[ 0 ]) # Driver Code X, Y, Z = 3 , 4 , 5 # Declare 3D array of characters matrix = [[[ 'a' , 'b' , 'c' , 'd' , 'e' ], [ 'f' , 'g' , 'h' , 'i' , 'k' ], [ 'a' , 'c' , 'd' , 'e' , 's' ], [ 'e' , 'g' , 'e' , 's' , 'j' ]], [[ 's' , 'j' , 'r' , 's' , 'g' ], [ 's' , 't' , 'u' , 'e' , 'y' ], [ 't' , 'y' , 'g' , 'j' , 'l' ], [ 'd' , 'r' , 'g' , 't' , 'j' ]], [[ 'e' , 'y' , 'r' , 'v' , 'n' ], [ 'q' , 'r' , 'y' , 'e' , 'w' ], [ 'k' , 'e' , 'u' , 'p' , 'q' ], [ 'z' , 'v' , 'a' , 's' , 'd' ]]] # Function Call findFreq(X, Y, Z, matrix) # This code is contributed by phasing17 |
C#
// C# program to implement above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to find frequency in 3-D matrix static void findFreq( int X, int Y, int Z, char [][][] matrix) { // Initializing unordered map Dictionary< char , int > freq = new Dictionary< char , int >(); for ( int i = 0 ; i < X ; i++) { for ( int j = 0 ; j < Y ; j++) { for ( int k = 0 ; k < Z ; k++) { if (!freq.ContainsKey(matrix[i][j][k])){ freq.Add(matrix[i][j][k], 1); } else { freq[(matrix[i][j][k])] += 1; } } } } // Get the size of the freq hashmap // to declare a new array int size = freq.Count; // Store the frequency in 2d array v pair[] v = new pair[size]; for ( int i = 0 ; i < size ; i++){ v[i] = new pair(0, 0); } int index = 0; foreach (KeyValuePair< char , int > mapElement in freq){ v[index].first = ( int )mapElement.Key; v[index].second = mapElement.Value; index++; } // Sort the frequency array // based on the frequencies Array.Sort(v, new Comp()); for ( int i = 0; i < size; i++) { Console.WriteLine(( char )v[i].first + " " + v[i].second); } } public static void Main( string [] args){ // Drivers code int X = 3, Y = 4, Z = 5; // Declare 3D array of characters char [][][] matrix = new char [][][]{ new char [][]{ new char []{ 'a' , 'b' , 'c' , 'd' , 'e' }, new char []{ 'f' , 'g' , 'h' , 'i' , 'k' }, new char []{ 'a' , 'c' , 'd' , 'e' , 's' }, new char []{ 'e' , 'g' , 'e' , 's' , 'j' } }, new char [][]{ new char []{ 's' , 'j' , 'r' , 's' , 'g' }, new char []{ 's' , 't' , 'u' , 'e' , 'y' }, new char []{ 't' , 'y' , 'g' , 'j' , 'l' }, new char []{ 'd' , 'r' , 'g' , 't' , 'j' } }, new char [][]{ new char []{ 'e' , 'y' , 'r' , 'v' , 'n' }, new char []{ 'q' , 'r' , 'y' , 'e' , 'w' }, new char []{ 'k' , 'e' , 'u' , 'p' , 'q' }, new char []{ 'z' , 'v' , 'a' , 's' , 'd' } } }; // Function call findFreq(X, Y, Z, matrix); } } // Class for pair public class pair{ public int first; public int second; // Constructor public pair( int f, int s) { this .first = f; this .second = s; } } class Comp : IComparer<pair>{ public int Compare(pair a, pair b) { if (a.second == b.second){ return a.first-b.first; } return a.second-b.second; } } // This code is contributed by subhamgoyal2014. |
Javascript
<script> // JavaScript implementation of the above approach // Function to find frequency in 3-D matrix function findFreq(X, Y, Z,matrix) { // Initializing unordered map let freq = new Map(); for (let i = 0; i < X; i++) { for (let j = 0; j < Y; j++) { for (let k = 0; k < Z; k++) { if (!freq.has(matrix[i][j][k])) freq.set(matrix[i][j][k],1) else freq.set(matrix[i][j][k],freq.get(matrix[i][j][k])+1) } } } // Store the frequency in vector let v = []; for (let [p,q] of freq) { v.push([q,p]); } // Sort the frequency vector v.sort(); for (let p of v) document.write(`${p[1]} ${p[0]}`, "</br>" ); } // Drivers code let X = 3, Y = 4, Z = 5; // Declare 3D array of characters let matrix = [ [ [ 'a' , 'b' , 'c' , 'd' , 'e' ], [ 'f' , 'g' , 'h' , 'i' , 'k' ], [ 'a' , 'c' , 'd' , 'e' , 's' ], [ 'e' , 'g' , 'e' , 's' , 'j' ] ], [ [ 's' , 'j' , 'r' , 's' , 'g' ], [ 's' , 't' , 'u' , 'e' , 'y' ], [ 't' , 'y' , 'g' , 'j' , 'l' ], [ 'd' , 'r' , 'g' , 't' , 'j' ] ], [ [ 'e' , 'y' , 'r' , 'v' , 'n' ], [ 'q' , 'r' , 'y' , 'e' , 'w' ], [ 'k' , 'e' , 'u' , 'p' , 'q' ], [ 'z' , 'v' , 'a' , 's' , 'd' ] ] ]; // Function call findFreq(X, Y, Z, matrix); // This code is written by // shinjanpatra </script> |
b 1 f 1 h 1 i 1 l 1 n 1 p 1 w 1 z 1 c 2 k 2 q 2 u 2 v 2 a 3 t 3 d 4 j 4 r 4 y 4 g 5 s 6 e 8
Time Complexity: O(N*M*P)
Auxiliary Space: O(1) As the map will have at most 26 values