Length of smallest subarray consisting of all occurrences of all maximum occurring elements
Given an array arr[] of size N, The task is to find the length of the smallest subarray consisting of all the occurrences of maximum occurring elements
Examples:
Input: arr[] = {1, 2, 1, 3, 2}
Output: 5
Explanation: Elements with maximum frequency (=2) are 1 & 2.
Therefore, the length of smallest subarray consisting of all the occurrences of 1 and 2 is 5 i.e {1, 2, 1, 3, 2}Input: arr[] = {1, 2, 5, 1, 5, 5}
Output: 4
Approach: The task can be solved by keeping track of the first & the last occurrences of the maximum occurring elements. The length of the smallest subarray would be the difference between the maximum of the last occurrences and the minimum of the first occurrences.
Follow the below steps to solve the problem:
- Create a map, to store the frequencies of the elements
- Find the elements with maximum frequency, and store their first and last occurrences.
- Finally, return the difference between the maximum of the last occurrences and the minimum of the first occurrences
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the length of smallest // subarray consisting of all the occurrences // of maximum occurring elements int get( int arr[], int n) { // Stores the frequencies unordered_map< int , int > occ; // Stores the maximum frequency int mx = -1; for ( int i = 0; i < n; i++) { occ[arr[i]]++; mx = max(mx, occ[arr[i]]); } // Stores the maximum occurring elements unordered_map< int , int > chk; for ( auto x : occ) { if (x.second == mx) chk[x.first]++; } // Stores the minimum of first occurrences // and maximum of last occurrences // of all the maximum occurring elements int fr = INT_MAX, sc = INT_MIN; for ( int i = 0; i < n; i++) { // Maximum occurring element if (chk.find(arr[i]) != chk.end()) { fr = min(fr, i); sc = max(sc, i); } } return sc - fr + 1; } // Driver Code int main() { int arr[] = { 1, 2, 5, 1, 5, 5 }; int n = sizeof (arr) / sizeof (arr[0]); cout << get(arr, n); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the length of smallest // subarray consisting of all the occurrences // of maximum occurring elements static int get( int arr[], int n) { // Stores the frequencies HashMap<Integer,Integer> occ = new HashMap<Integer,Integer>(); // Stores the maximum frequency int mx = - 1 ; for ( int i = 0 ; i < n; i++) { if (occ.containsKey(arr[i])){ occ.put(arr[i], occ.get(arr[i])+ 1 ); } else { occ.put(arr[i], 1 ); } mx = Math.max(mx, occ.get(arr[i])); } // Stores the maximum occurring elements HashMap<Integer,Integer> chk= new HashMap<Integer,Integer>(); for (Map.Entry<Integer,Integer> x : occ.entrySet()) { if (x.getValue() == mx) if (chk.containsKey(x.getKey())){ chk.put(x.getKey(), chk.get(x.getKey())+ 1 ); } else { chk.put(x.getKey(), 1 ); } } // Stores the minimum of first occurrences // and maximum of last occurrences // of all the maximum occurring elements int fr = Integer.MAX_VALUE, sc = Integer.MIN_VALUE; for ( int i = 0 ; i < n; i++) { // Maximum occurring element if (chk.containsKey(arr[i])) { fr = Math.min(fr, i); sc = Math.max(sc, i); } } return sc - fr + 1 ; } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 5 , 1 , 5 , 5 }; int n = arr.length; System.out.print(get(arr, n)); } } // This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approach import sys from collections import defaultdict # Function to find the length of smallest # subarray consisting of all the occurrences # of maximum occurring elements def get(arr, n): # Stores the frequencies occ = defaultdict( int ) # Stores the maximum frequency mx = - 1 for i in range (n): occ[arr[i]] + = 1 mx = max (mx, occ[arr[i]]) # Stores the maximum occurring elements chk = defaultdict( int ) for x in occ: if (occ[x] = = mx): chk[x] + = 1 # Stores the minimum of first occurrences # and maximum of last occurrences # of all the maximum occurring elements fr = sys.maxsize sc = - sys.maxsize for i in range (n): # Maximum occurring element if (arr[i] in chk): fr = min (fr, i) sc = max (sc, i) return sc - fr + 1 # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 5 , 1 , 5 , 5 ] n = len (arr) print (get(arr, n)) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { // Function to find the length of smallest // subarray consisting of all the occurrences // of maximum occurring elements static int get ( int []arr, int n) { // Stores the frequencies Dictionary< int , int > occ = new Dictionary< int , int >(); // Stores the maximum frequency int mx = -1; for ( int i = 0; i < n; i++) { if (occ.ContainsKey(arr[i])) { occ[arr[i]] = occ[arr[i]] + 1; } else { occ.Add(arr[i], 1); } mx = Math.Max(mx, occ[arr[i]]); } // Stores the maximum occurring elements Dictionary< int , int > chk = new Dictionary< int , int >(); foreach (KeyValuePair< int , int > x in occ){ if (x.Value == mx){ if (chk.ContainsKey(x.Key)){ chk[x.Key] = chk[x.Key] + 1; } else { chk.Add(x.Key, 1); } } } // Stores the minimum of first occurrences // and maximum of last occurrences // of all the maximum occurring elements int fr = Int32.MaxValue, sc = Int32.MinValue; for ( int i = 0; i < n; i++) { // Maximum occurring element if (chk.ContainsKey(arr[i])) { fr = Math.Min(fr, i); sc = Math.Max(sc, i); } } return sc - fr + 1; } // Driver Code public static void Main() { int []arr = { 1, 2, 5, 1, 5, 5 }; int n = arr.Length; Console.Write( get (arr, n)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the length of smallest // subarray consisting of all the occurrences // of maximum occurring elements function get(arr, n) { // Stores the frequencies let occ = new Map(); // Stores the maximum frequency let mx = -1; for (let i = 0; i < n; i++) { if (occ.has(arr[i])) { occ.set(arr[i], occ.get(arr[i]) + 1) } else { occ.set(arr[i], 1) } mx = Math.max(mx, occ.get(arr[i])); } // Stores the maximum occurring elements let chk = new Map(); for (let [key, val] of occ) { if (val == mx) chk.set(key, chk.get(key) + 1) } // Stores the minimum of first occurrences // and maximum of last occurrences // of all the maximum occurring elements let fr = Number.MAX_VALUE, sc = Number.MIN_VALUE; for (let i = 0; i < n; i++) { // Maximum occurring element if (chk.has(arr[i])) { fr = Math.min(fr, i); sc = Math.max(sc, i); } } return sc - fr + 1; } // Driver Code let arr = [1, 2, 5, 1, 5, 5]; let n = arr.length; document.write(get(arr, n)); // This code is contributed by Potta Lokesh </script> |
4
Time Complexity: O(N)
Auxiliary Space: O(N)