Smallest subarray with all occurrences of a most frequent element
Given an array, A. Let x be an element in the array. x has the maximum frequency in the array. Find the smallest subsegment of the array which also has x as the maximum frequency element.
Examples:
Input : arr[] = {4, 1, 1, 2, 2, 1, 3, 3} Output : 1, 1, 2, 2, 1 The most frequent element is 1. The smallest subarray that has all occurrences of it is 1 1 2 2 1 Input : A[] = {1, 2, 2, 3, 1} Output : 2, 2 Note that there are two elements that appear two times, 1 and 2. The smallest window for 1 is whole array and smallest window for 2 is {2, 2}. Since window for 2 is smaller, this is our output.
Approach:
Observe that if X is the maximum repeated element of our subsegment then the subsegment should look like this [X, ….., X], cause if the subsegment end or begins with another element we can delete it which does not alter our answer.
To solve this problem, let us store for every distinct element in the array three values, index of the first occurrence of the element and the index of the last occurrence the element and the frequency of the element. And at every step for a maximum repeated element minimize the size of our subsegment.
C++
// C++ implementation to find smallest // subarray with all occurrences of // a most frequent element #include <bits/stdc++.h> using namespace std; void smallestSubsegment( int a[], int n) { // To store left most occurrence of elements unordered_map< int , int > left; // To store counts of elements unordered_map< int , int > count; // To store maximum frequency int mx = 0; // To store length and starting index of // smallest result window int mn, strindex; for ( int i = 0; i < n; i++) { int x = a[i]; // First occurrence of an element, // store the index if (count[x] == 0) { left[x] = i; count[x] = 1; } // increase the frequency of elements else count[x]++; // Find maximum repeated element and // store its last occurrence and first // occurrence if (count[x] > mx) { mx = count[x]; mn = i - left[x] + 1; // length of subsegment strindex = left[x]; } // select subsegment of smallest size else if (count[x] == mx && i - left[x] + 1 < mn) { mn = i - left[x] + 1; strindex = left[x]; } } // Print the subsegment with all occurrences of // a most frequent element for ( int i = strindex; i < strindex + mn; i++) cout << a[i] << " " ; } // Driver code int main() { int A[] = { 1, 2, 2, 2, 1 }; int n = sizeof (A) / sizeof (A[0]); smallestSubsegment(A, n); return 0; } |
Java
// Java implementation to find smallest // subarray with all occurrences of // a most frequent element import java.io.*; import java.util.*; class GfG { static class Pair{ int fre; int fi; int li; Pair( int fre, int fi, int li){ this .fre=fre; this .fi=fi; this .li=li; } } static void smallestSubsegment( int arr[], int n) { // To store left most occurrence of elements HashMap<Integer,Pair>hm= new HashMap<>(); int mfi=arr[ 0 ]; int mf= 1 ; int si= 0 ; int mflen= 1 ; hm.put(arr[ 0 ], new Pair( 1 , 0 , 0 )); for ( int i= 1 ;i<arr.length;i++){ int val=arr[i]; if (hm.containsKey(val)) { Pair p=hm.get(val); p.fre++; p.li=i; int len=i-p.fi+ 1 ; if (p.fre>mf){ mfi=val; mf=p.fre; si=p.fi; mflen=len; } else if (p.fre==mf && len<mflen){ mfi=val; mf=p.fre; si=p.fi; mflen=len; } else if (p.fre==mf && len==mflen && p.fi<si) { mfi=val; mf=p.fre; si=p.fi; mflen=len; } } else hm.put(val, new Pair( 1 ,i,i)); } int en=mflen+si- 1 ; // Print the subsegment with all occurrences of // a most frequent element for ( int i = si; i <=en ; i++) System.out.print(arr[i] + " " ); } // Driver program public static void main (String[] args) { int A[] = { 1 , 2 , 2 , 2 , 1 }; int n = A.length; smallestSubsegment(A, n); } } // This code is contributed by waris amir |
Python3
# Python3 implementation to find smallest # subarray with all occurrences of # a most frequent element def smallestSubsegment(a, n): # To store left most occurrence of elements left = dict () # To store counts of elements count = dict () # To store maximum frequency mx = 0 # To store length and starting index of # smallest result window mn, strindex = 0 , 0 for i in range (n): x = a[i] # First occurrence of an element, # store the index if (x not in count.keys()): left[x] = i count[x] = 1 # increase the frequency of elements else : count[x] + = 1 # Find maximum repeated element and # store its last occurrence and first # occurrence if (count[x] > mx): mx = count[x] mn = i - left[x] + 1 # length of subsegment strindex = left[x] # select subsegment of smallest size elif (count[x] = = mx and i - left[x] + 1 < mn): mn = i - left[x] + 1 strindex = left[x] # Print the subsegment with all occurrences of # a most frequent element for i in range (strindex, strindex + mn): print (a[i], end = " " ) # Driver code A = [ 1 , 2 , 2 , 2 , 1 ] n = len (A) smallestSubsegment(A, n) # This code is contributed by Mohit Kumar |
C#
// C# implementation to find smallest // subarray with all occurrences of // a most frequent element using System; using System.Collections.Generic; class GfG { static void smallestSubsegment( int []a, int n) { // To store left most occurrence of elements Dictionary< int , int > left = new Dictionary< int , int >(); // To store counts of elements Dictionary< int , int > count = new Dictionary< int , int >(); // To store maximum frequency int mx = 0; // To store length and starting index of // smallest result window int mn = -1, strindex = -1; for ( int i = 0; i < n; i++) { int x = a[i]; // First occurrence of an element, // store the index if (!count.ContainsKey(x)) { left.Add(x, i) ; count.Add(x, 1); } // increase the frequency of elements else count[x] = count[x] + 1; // Find maximum repeated element and // store its last occurrence and first // occurrence if (count[x] > mx) { mx = count[x]; // length of subsegment mn = i - left[x] + 1; strindex = left[x]; } // select subsegment of smallest size else if ((count[x] == mx) && (i - left[x] + 1 < mn)) { mn = i - left[x] + 1; strindex = left[x]; } } // Print the subsegment with all occurrences of // a most frequent element for ( int i = strindex; i < strindex + mn; i++) Console.Write(a[i] + " " ); } // Driver code public static void Main (String[] args) { int []A = { 1, 2, 2, 2, 1 }; int n = A.Length; smallestSubsegment(A, n); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript implementation to find smallest // subarray with all occurrences of // a most frequent element function smallestSubsegment(a,n) { // To store left most occurrence of elements let left= new Map(); // To store counts of elements let count= new Map(); // To store maximum frequency let mx = 0; // To store length and starting index of // smallest result window let mn = -1, strindex = -1; for (let i = 0; i < n; i++) { let x = a[i]; // First occurrence of an element, // store the index if (count.get(x) == null ) { left.set(x, i) ; count.set(x, 1); } // increase the frequency of elements else count.set(x, count.get(x) + 1); // Find maximum repeated element and // store its last occurrence and first // occurrence if (count.get(x) > mx) { mx = count.get(x); // length of subsegment mn = i - left.get(x) + 1; strindex = left.get(x); } // select subsegment of smallest size else if ((count.get(x) == mx) && (i - left.get(x) + 1 < mn)) { mn = i - left.get(x) + 1; strindex = left.get(x); } } // Print the subsegment with all occurrences of // a most frequent element for (let i = strindex; i < strindex + mn; i++) document.write(a[i] + " " ); } // Driver program let A=[1, 2, 2, 2, 1]; let n = A.length; smallestSubsegment(A, n); // This code is contributed by unknown2108 </script> |
Output:
2 2 2
Time Complexity: O(n)
As we are doing linear operations on the given array.
Auxiliary Space: O(n)
The extra space is used to store the elements in the map, which in worst case can go upto O(n) when all elements are distinct.
Contact Us