Maximum frequencies in each M-length subarray
Given an array arr[] consisting of N integers and a positive integer M, the task is to find the maximum frequency for each M-length subarray ( 0 < M ? N).
Examples:
Input: arr[] = {1, 2, 3, 1, 2, 4, 1, 4, 4}, M = 4
Output: 2 2 1 2 2 3
Explanation:
All the M length sub-arrays with the maximum frequency of any element are:
- {1, 2, 3, 1}, The maximum frequency of an element is 2.
- {2, 3, 1, 2}, The maximum frequency of an element is 2.
- {3, 1, 2, 4}, The maximum frequency of an element is 1.
- {1, 2, 4, 1}, The maximum frequency of an element is 2.
- {2, 4, 1, 4}, The maximum frequency of an element is 2.
- {4, 1, 4, 4}, The maximum frequency of an element is 3.
Input: arr[] = {1, 1, 2, 2, 3, 5}, M = 4
Output: 2 2 2
Approach: The given problem can be solved by finding the frequencies for each M-sized sub-array print the maximum frequency among all. Follow the steps below to solve the given problem:
- Initialize an unordered map, say M to stores the frequencies of array elements.
- Initialize the variable, say val as 0 to store the maximum frequency of an element of the subarray.
- Iterate over the range [0, N] using the variable i and perform the following steps:
- If the value of (i – M) is greater than equal to 0, then decrease the value of A[i – M] from the map M.
- Add the value of arr[i] in the map M.
- Iterate over the map M and update the value of val as the maximum of val or x.second.
- Print the value of val as the maximum for the present M-sized subarray.
Below is an implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the frequency of // the most common element in each M // length subarrays void maxFrequencySubarrayUtil( vector< int > A, int N, int M) { int i = 0; // Stores frequency of array element unordered_map< int , int > m; // Stores the maximum frequency int val = 0; // Iterate for the first sub-array // and store the maximum for (; i < M; i++) { m[A[i]]++; val = max(val, m[A[i]]); } // Print the maximum frequency for // the first subarray cout << val << " " ; // Iterate over the range [M, N] for (i = M; i < N; i++) { // Subtract the A[i - M] and // add the A[i] in the map m[A[i - M]]--; m[A[i]]++; val = 0; // Find the maximum frequency for ( auto x : m) { val = max(val, x.second); } // Print the maximum frequency // for the current subarray cout << val << " " ; } } // Driver Code int main() { vector< int > A = { 1, 1, 2, 2, 3, 5 }; int N = A.size(); int M = 4; maxFrequencySubarrayUtil(A, N, M); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the frequency of // the most common element in each M // length subarrays static void maxFrequencySubarrayUtil( int [] A, int N, int M) { int i = 0 ; // Stores frequency of array element HashMap<Integer, Integer> m = new HashMap<Integer, Integer>(); // Stores the maximum frequency int val = 0 ; // Iterate for the first sub-array // and store the maximum for (; i < M; i++) { if (m.containsKey(A[i])) { m.put(A[i], m.get(A[i]) + 1 ); } else { m.put(A[i], 1 ); } val = Math.max(val, m.get(A[i])); } // Print the maximum frequency for // the first subarray System.out.print(val + " " ); // Iterate over the range [M, N] for (i = M; i < N; i++) { // Subtract the A[i - M] and // add the A[i] in the map if (m.containsKey(i - M)) { m.put(i - M, m.get(i - M) - 1 ); } if (m.containsKey(A[i])) { m.put(A[i], m.get(A[i]) + 1 ); } else { m.put(A[i], 1 ); } val = 0 ; // Find the maximum frequency for (Map.Entry<Integer, Integer> x : m.entrySet()) { val = Math.max(val, x.getValue()); } // Print the maximum frequency // for the current subarray System.out.print(val + " " ); } } // Driver Code public static void main(String[] args) { int [] A = { 1 , 1 , 2 , 2 , 3 , 5 }; int N = A.length; int M = 4 ; maxFrequencySubarrayUtil(A, N, M); } } // This code is contributed by 29AjayKumar |
Python3
# Python 3 program for the above approach # Function to find the frequency of # the most common element in each M # length subarrays def maxFrequencySubarrayUtil(A,N,M): i = 0 # Stores frequency of array element m = {} # Stores the maximum frequency val = 0 # Iterate for the first sub-array # and store the maximum while (i < M): if A[i] in m: m[A[i]] + = 1 else : m[A[i]] = 1 val = max (val, m[A[i]]) i + = 1 # Print the maximum frequency for # the first subarray print (val,end = " " ) # Iterate over the range [M, N] for i in range (M,N, 1 ): # Subtract the A[i - M] and # add the A[i] in the map if A[i - M] in m: m[A[i - M]] - = 1 else : m[A[i - M]] = 0 if A[i] in m: m[A[i]] + = 1 val = 0 # Find the maximum frequency for key,value in m.items(): val = max (val, value) # Print the maximum frequency # for the current subarray print (val,end = " " ) # Driver Code if __name__ = = '__main__' : A = [ 1 , 1 , 2 , 2 , 3 , 5 ] N = len (A) M = 4 maxFrequencySubarrayUtil(A, N, M) # This code is contributed by ipg2016107. |
C#
using System; using System.Collections.Generic; public class GFG { // Function to find the frequency of // the most common element in each M // length subarrays static void maxFrequencySubarrayUtil( int [] A, int N, int M) { int i = 0; // Stores frequency of array element Dictionary< int , int > m = new Dictionary< int , int >(); // Stores the maximum frequency int val = 0; // Iterate for the first sub-array // and store the maximum for (; i < M; i++) { if (m.ContainsKey(A[i])) { val = m[A[i]]; m.Remove(A[i]); m.Add(A[i], val + 1); } else { m.Add(A[i], 1); } val = Math.Max(val, m[A[i]]); } // Print the maximum frequency for // the first subarray Console.Write(val + " " ); // Iterate over the range [M, N] for (i = M; i < N; i++) { // Subtract the A[i - M] and // add the A[i] in the map if (m.ContainsKey(i - M)) { val = i - M; m.Remove(i - M); m.Add(i - M, val - 1); } if (m.ContainsKey(A[i])) { val = m[A[i]]; m.Remove(A[i]); m.Add(A[i], val + 1); } else { m.Add(A[i], 1); } val = Math.Max(val, m[A[i]]); val = 0; // Find the maximum frequency foreach (KeyValuePair< int , int > x in m) { val = Math.Max(val, x.Value); } // Print the maximum frequency // for the current subarray Console.Write(val + " " ); } } // Driver Code static public void Main() { int [] A = { 1, 1, 2, 2, 3, 5 }; int N = 6; int M = 4; maxFrequencySubarrayUtil(A, N, M); } } // This code is contributed by maddler. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the frequency of // the most common element in each M // length subarrays function maxFrequencySubarrayUtil(A, N, M) { // Stores frequency of array element let m = new Map(); // Stores the maximum frequency let val = 0; // Iterate for the first sub-array // and store the maximum for (let i = 0; i < M; i++) { if (m.has(A[i])) { m.set(m.get(A[i]), m.get(A[i]) + 1); } else { m.set(A[i], 1); } val = Math.max(val, m.get(A[i])); } // Print the maximum frequency for // the first subarray document.write(val + " " ); // Iterate over the range [M, N] for (i = M; i < N; i++) { // Subtract the A[i - M] and // add the A[i] in the map if (m.has(A[i - m])) m.set(m.get(A[i - M]), m.get(A[i - M]) - 1); if (m.has(A[i])) m.set(m.get(A[i]), m.get(A[i]) + 1); val = 0; // Find the maximum frequency for (let [key, value] of m) { val = Math.max(val, value); } // Print the maximum frequency // for the current subarray document.write(val + " " ); } } // Driver Code let A = [1, 1, 2, 2, 3, 5]; let N = A.length; let M = 4; maxFrequencySubarrayUtil(A, N, M); // This code is contributed by Potta Lokesh </script> |
Output:
2 2 2
Time Complexity: O(N*M)
Auxiliary Space: O(M)
Contact Us