Smallest Subarray With all Occurrences of a Most Frequent Element  

Difficulty Level Medium
Frequently asked in Citrix Coursera OYO Rooms Qualtrics Synopsys Taxi4Sure
Array Hash

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.

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.

Please click Like if you loved this article?

smallest subarray with the most frequent elementPin

Algorithm for smallest subarray with the most frequent element  

  1. Declare two HashMaps.
  2. Set maxfreq, minlen, winindex to 0.
  3. While 0 < n
    1. Count and store the frequency of array numbers into the map in every iteration.
    2. 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]];
    3. 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]];
  4. print the array from winindex to winindex + minlen
See also
Cumulative Frequency of Count of Each Element in an Unsorted Array

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

Please click Like if you loved this article?

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.

Please click Like if you loved this article?

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.

See also
Check if two arrays are equal or not

maxfreq=3, minlen = i – freqCount[a[i]] + 1 = 3, winindex =1

Please click Like if you loved this article?

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.

See also
Count quadruples from four sorted arrays whose sum is equal to a given value x

Space Complexity

O(n) where “n” is the number of elements in the array.

References

Please click Like if you loved this article?

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh