In the smallest subarray with all occurrences of a most frequent element problem, we have given an array. Take a number “m” in an array with the maximum frequency. The problem statement says that you have to find out the smallest subarray which also has all the occurrence of number “m” in that smallest sub-array.
Table of Contents
Example
Input
[3, 5, 4, 5, 4]
Output
[5, 4, 5]
Explanation
As in this, there are two frequent elements with the same frequency so it will take first occurred element and make the smallest sub-array.
Algorithm for smallest subarray with the most frequent element
- Declare two HashMaps.
- Set maxfreq, minlen, winindex to 0.
- While 0 < n
- Count and store the frequency of array numbers into the map in every iteration.
- Check if the current element has a frequency greater than maxfreq, if true, then do the following:
- maxFreq = count[a[i]];
- minlen = i – freqCount[a[i]] + 1;
- winindex = freqCount[a[i]];
- else if the maximum frequency is same as current element frequency and also the length of the subarray so formed is less than the minlen, then do the following:
- minlen = i – freqCount[a[i]] + 1;
- winindex = freqCount[a[i]];
- print the array from winindex to winindex + minlen
Explanation for smallest subarray with the most frequent element
We have given a problem statement that we have to find out the smallest sub-array which should have all the occurrence of the most frequent element. We will declare a maxFreq for storing the max frequency of elements as an index, “minlen” for determining the minimum length of sub-array, and “winindex” for the smallest subarray. If element found for the first time then insert both of the maps, if it is repeated element in a map then store it in the count map.
We will start to store the element and its index for each iteration and store it to map and then check if the current element has a value greater than “maxfreq” we will update the value of maxFreq and “minlen”.
If the frequency of the element is the same as the “maxfreq” we will check the length of the subarray, and update it, if conditions satisfy.
Let us consider an example for smallest subarray with all occurrences of a most frequent element :
Example
arr={1, 2, 2, 2, 1}
i=0 => arr[i]=1
freqCount=[1:0] count= [1:1]
maxfreq=1, minlen = i – freqCount[a[i]] + 1 = 1, winindex =0
we will update the maxfreq and minlen and windex
i = 1 => arr[ i ] = 2
freqCount=[1:0,2:1] count= [1:1, 2:1], nothing excecutes
i = 2 => arr[ i ] = 2
freqCount=[1:0,2:1] count= [1:0, 2:2], it update only count.
maxfreq=2, minlen = i – freqCount[a[i]] + 1 = 2, winindex =1
i = 3 => arr[ i ] = 2
freqCount=[1:0,2:1] count= [1:0, 2:3], it update only count.
maxfreq=3, minlen = i – freqCount[a[i]] + 1 = 3, winindex =1
i = 4 => arr[ i ] = 1
freqCount=[1:0,2:1] count= [1:1, 2:3], it update only count.
maxfreq=3, minlen = i – freqCount[a[i]] + 1 = 3, winindex =1
we have our value that is minlen=3 and winindex =1
Loop opens and it will goes on from winindex to minlen+winindex i.e, from 1 to less than 4
And it will print [ 2 2 2 ], that is our required answer
Implementation for smallest subarray with the most frequent element
C++ Program
#include <unordered_map>
#include<iostream>
using namespace std;
void frequentSubArray(int a[], int n)
{
unordered_map<int, int> freqCount;
unordered_map<int, int> count;
int maxFreq = 0;
int minlen, winindex;
for (int i = 0; i < n; i++)
{
if (count[a[i]] == 0)
{
freqCount[a[i]] = i;
count[a[i]] = 1;
}
else
count[a[i]]++;
if (count[a[i]] > maxFreq)
{
maxFreq = count[a[i]];
minlen = i - freqCount[a[i]] + 1;
winindex = freqCount[a[i]];
}
else if (count[a[i]] == maxFreq && i - freqCount[a[i]] + 1 < minlen)
{
minlen = i - freqCount[a[i]] + 1;
winindex = freqCount[a[i]];
}
}
for (int i = winindex; i < winindex + minlen; i++)
{
cout << a[i] << " ";
}
}
int main()
{
int A[] = { 1, 2, 2, 2, 1 };
int n = sizeof(A) / sizeof(A[0]);
frequentSubArray(A, n);
return 0;
}
2 2 2
Java Program
import java.io.*;
import java.util.*;
class mostFrequentSubArray
{
public static void frequentSubArray(int a[], int n)
{
HashMap<Integer, Integer> freqCount= new HashMap<Integer, Integer>();
HashMap<Integer, Integer> count= new HashMap<Integer, Integer>();
int maxFreq = 0;
int minlen = -1, winindex = -1;
for (int i = 0; i < n; i++)
{
if (count.containsKey(a[i]))
{
count.put(a[i], count.get(a[i]) + 1);
}
else
{
freqCount.put(a[i], i) ;
count.put(a[i], 1);
}
if (count.get(a[i]) > maxFreq)
{
maxFreq = count.get(a[i]);
minlen = i - freqCount.get(a[i]) + 1;
winindex = freqCount.get(a[i]);
}
else if ((count.get(a[i]) == maxFreq) && (i - freqCount.get(a[i]) + 1 < minlen))
{
minlen = i - freqCount.get(a[i]) + 1;
winindex = freqCount.get(a[i]);
}
}
for (int i = winindex; i < winindex + minlen; i++)
System.out.print(a[i] + " ");
}
public static void main (String[] args)
{
int arr[] = { 1, 2, 2, 2, 1 };
int n = arr.length;
frequentSubArray(arr, n);
}
}
2 2 2
Complexity Analysis for smallest subarray with the most frequent element
Time Complexity
O(n) where “n” is the number of elements in the array.
Space Complexity
O(n) where “n” is the number of elements in the array.