Maximum frequencies in each M-length subarray

0 0 6 minutes read

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)

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 zambiatek!