Smallest Subarray With all Occurrences of a Most Frequent Element

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

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.

smallest subarray with the most frequent element

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

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.

References

Translate »