Given an array arr[] of N integers, the task is to find the size of the largest subarray with frequency of all elements the same.
Examples:
Input: arr[] = {1, 2, 2, 5, 6, 5, 6}
Output: 6
Explanation:
The subarray = {2, 2, 5, 6, 5, 6} has frequency of every element is 2.Input: arr[] = {1, 1, 1, 1, 1}
Output: 5
Explanation:
The subarray = {1, 1, 1, 1, 1} has frequency of every element is 5.
Approach: The idea is to generate all possible subarrays and check for each subarray whether any subarray has frequency of all elements or not. Below are the steps:
- Generate all possible subarrays.
- For each subarray, take two maps, one map to stores the frequency of every element and second map stores number of elements with given frequency.
- If for any subarray, size of second map becomes equal to 1, that means every element have same frequency in the subarray.
- Return the maximum size of all such subarrays.
Below is the implementation of above approach:
C++
// C++ program for the above approach#include <iostream>#include <unordered_map>using namespace std;// Function to find maximum subarray sizeint max_subarray_size(int N, int arr[]){ int ans = 0; // Generating all subarray // i -> starting index // j -> end index for (int i = 0; i < N; i++) { // Map 1 to hash frequency // of all elements in subarray unordered_map<int, int> map1; // Map 2 to hash frequency // of all frequencies of // elements unordered_map<int, int> map2; for (int j = i; j < N; j++) { // ele_count is the previous // frequency of arr[j] int ele_count; // Finding previous frequency of // arr[j] in map 1 if (map1.find(arr[j]) == map1.end()) { ele_count = 0; } else { ele_count = map1[arr[j]]; } // Increasing frequency of arr[j] // by 1 map1[arr[j]]++; // Check if previous frequency // is present in map 2 if (map2.find(ele_count) != map2.end()) { // Delete previous frequency // if hash is equal to 1 if (map2[ele_count] == 1) { map2.erase(ele_count); } else { // Decrement the hash of // previous frequency map2[ele_count]--; } } // Incrementing hash of new // frequency in map 2 map2[ele_count + 1]++; // Check if map2 size is 1 // and updating answer if (map2.size() == 1) ans = max(ans, j - i + 1); } } // Return the maximum size of subarray return ans;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 2, 2, 5, 6, 5, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << max_subarray_size(N, arr); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find maximum subarray size static int max_subarray_size(int N, int[] arr) { int ans = 0; // Generating all subarray // i -> starting index // j -> end index for(int i = 0; i < N; i++) { // Map 1 to hash frequency // of all elements in subarray HashMap<Integer, Integer> map1 = new HashMap<>(); // Map 2 to hash frequency // of all frequencies of // elements HashMap<Integer, Integer> map2 = new HashMap<>(); for(int j = i; j < N; j++) { // ele_count is the previous // frequency of arr[j] int ele_count; // Finding previous frequency of // arr[j] in map 1 if (!map1.containsKey(arr[j])) { ele_count = 0; } else { ele_count = map1.get(arr[j]); } // Increasing frequency of arr[j] // by 1 if (map1.containsKey(arr[j])) { map1.put(arr[j],map1.get(arr[j])+1); } else { map1.put(arr[j], 1); } // Check if previous frequency // is present in map 2 if (map2.containsKey(ele_count)) { // Delete previous frequency // if hash is equal to 1 if (map2.get(ele_count) == 1) { map2.remove(ele_count); } else { // Decrement the hash of // previous frequency map2.put(ele_count,map2.get(ele_count) - 1); } } // Incrementing hash of new // frequency in map 2 if (map2.containsKey(ele_count + 1)) { map2.put(ele_count + 1, map2.get(ele_count + 1) + 1); } else { map2.put(ele_count + 1, 1); } // Check if map2 size is 1 // and updating answer if (map2.size() == 1) ans = Math.max(ans, j - i + 1); } } // Return the maximum size of subarray return ans; } // Driver Code public static void main(String []args) { // Given array arr[] int[] arr = { 1, 2, 2, 5, 6, 5, 6 }; int N = arr.length; // Function Call System.out.println(max_subarray_size(N, arr)); }}// This code is contributed by rutvik_56. |
Python3
# Python3 program for the above approach# Function to find maximum subarray sizedef max_subarray_size(N, arr): ans = 0 # Generating all subarray # i -> starting index # j -> end index for i in range(N): # Map 1 to hash frequency # of all elements in subarray map1 = {} # Map 2 to hash frequency # of all frequencies of # elements map2 = {} for j in range(i, N): # ele_count is the previous # frequency of arr[j] # Finding previous frequency of # arr[j] in map 1 if (arr[j] not in map1): ele_count = 0 else: ele_count = map1[arr[j]] # Increasing frequency of arr[j] # by 1 if arr[j] in map1: map1[arr[j]] += 1 else: map1[arr[j]] = 1 # Check if previous frequency # is present in map 2 if (ele_count in map2): # Delete previous frequency # if hash is equal to 1 if (map2[ele_count] == 1): del map2[ele_count] else: # Decrement the hash of # previous frequency map2[ele_count] -= 1 # Incrementing hash of new # frequency in map 2 if ele_count + 1 in map2: map2[ele_count + 1] += 1 else: map2[ele_count + 1] = 1 # Check if map2 size is 1 # and updating answer if (len(map2) == 1): ans = max(ans, j - i + 1) # Return the maximum size of subarray return ans# Driver Code# Given array arr[]arr = [ 1, 2, 2, 5, 6, 5, 6 ]N = len(arr)# Function Callprint(max_subarray_size(N, arr))# This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approachusing System;using System.Collections.Generic; class GFG{ // Function to find maximum subarray sizestatic int max_subarray_size(int N, int[] arr){ int ans = 0; // Generating all subarray // i -> starting index // j -> end index for(int i = 0; i < N; i++) { // Map 1 to hash frequency // of all elements in subarray Dictionary<int, int> map1 = new Dictionary<int, int>(); // Map 2 to hash frequency // of all frequencies of // elements Dictionary<int, int> map2 = new Dictionary<int, int>(); for(int j = i; j < N; j++) { // ele_count is the previous // frequency of arr[j] int ele_count; // Finding previous frequency of // arr[j] in map 1 if (!map1.ContainsKey(arr[j])) { ele_count = 0; } else { ele_count = map1[arr[j]]; } // Increasing frequency of arr[j] // by 1 if (map1.ContainsKey(arr[j])) { map1[arr[j]]++; } else { map1.Add(arr[j], 1); } // Check if previous frequency // is present in map 2 if (map2.ContainsKey(ele_count)) { // Delete previous frequency // if hash is equal to 1 if (map2[ele_count] == 1) { map2.Remove(ele_count); } else { // Decrement the hash of // previous frequency map2[ele_count]--; } } // Incrementing hash of new // frequency in map 2 if (map2.ContainsKey(ele_count + 1)) { map2[ele_count + 1]++; } else { map2.Add(ele_count + 1, 1); } // Check if map2 size is 1 // and updating answer if (map2.Count == 1) ans = Math.Max(ans, j - i + 1); } } // Return the maximum size of subarray return ans;}// Driver Codestatic void Main() { // Given array arr[] int[] arr = { 1, 2, 2, 5, 6, 5, 6 }; int N = arr.Length; // Function Call Console.WriteLine(max_subarray_size(N, arr));}}// This code is contributed by divyesh072019 |
Javascript
<script>// JavaScript program for the above approach// Function to find maximum subarray sizefunction max_subarray_size(N, arr){ let ans = 0; // Generating all subarray // i -> starting index // j -> end index for (let i = 0; i < N; i++) { // Map 1 to hash frequency // of all elements in subarray let map1 = new Map(); // Map 2 to hash frequency // of all frequencies of // elements let map2 = new Map(); for (let j = i; j < N; j++) { // ele_count is the previous // frequency of arr[j] let ele_count; // Finding previous frequency of // arr[j] in map 1 if (!map1.has(arr[j])) { ele_count = 0; } else { ele_count = map1.get(arr[j]); } // Increasing frequency of arr[j] by 1 map1.set(arr[j],ele_count+1) // Check if previous frequency // is present in map 2 if (map2.has(ele_count)) { // Delete previous frequency // if hash is equal to 1 if (map2.get(ele_count) == 1) { map2.delete(ele_count); } else { // Decrement the hash of // previous frequency map2.set(ele_count,map2.get(ele_count)-1) } } // Incrementing hash of new // frequency in map 2 if(map2.get(ele_count+1) !== undefined){ map2.set(ele_count+1,map2.get(ele_count+1)+1); } else map2.set(ele_count+1,1); // Check if map2 size is 1 // and updating answer if (map2.size == 1){ ans = Math.max(ans, j - i + 1); } } } // Return the maximum size of subarray return ans;}// Driver Code// Given array arrconst arr = [ 1, 2, 2, 5, 6, 5, 6 ];const N = arr.length;// Function Calldocument.write(max_subarray_size(N, arr));// This code is contributed by shinjanpatra.</script> |
Output
6
Time Complexity: O(N2)
Auxiliary Space: O(N)
Naive Approach: Simple solution is to generate all subarrays and check whether each element has same frequency or not.
C++14
#include <bits/stdc++.h>using namespace std;//global variable to store the answerint ans=1;//function to check equal for all equal frequenciesint checkFreq(int *arr,int r,int l){ int i,count=1; //vector to store subarray vector<int>temp; //vector to store all frequencies of this subarray vector<int>freq; freq.clear(); temp.clear(); //insert all subarray elements for(i=r;i<=l;i++) temp.push_back(arr[i]); sort(temp.begin(),temp.end()); //counting equal consecutive elements to store frequencies for(i=0;i<temp.size();i++) { if(temp[i]==temp[i+1]) count++; else{ freq.push_back(count); count=1; } } //checking for all equal elements for(i=1;i<freq.size();i++) { if(freq[0]!=freq[i]) return -1; } return temp.size();}//code to generate all subarrays in n^2void generateSubArrays(int *arr,int start,int end,int len){ if(end==len) return; else if(start>end) generateSubArrays(arr,0,end+1,len); else{ ans=max(ans,checkFreq(arr,start,end)); generateSubArrays(arr,start+1,end,len); }}//drivers codeint main(){ int arr[]={ 1, 10, 5, 4, 4, 4, 10 }; int n=sizeof(arr)/sizeof(arr[0]); generateSubArrays(arr,0,0,n); cout<<ans; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG{ // Java code for the same approach// global variable to store the answerstatic int ans = 1;// function to check equal for all equal frequenciesstatic int checkFreq(int arr[], int r, int l){ int i, count = 1; // vector to store subarray ArrayList<Integer> temp = new ArrayList<>(); // vector to store all frequencies of this subarray ArrayList<Integer> freq = new ArrayList<>(); // insert all subarray elements for(i = r; i <= l; i++) temp.add(arr[i]); Collections.sort(temp); // counting equal consecutive elements to store frequencies for(i = 0; i < temp.size()-1; i++) { if(temp.get(i) == temp.get(i+1)) count++; else{ freq.add(count); count=1; } } // checking for all equal elements for(i = 1; i < freq.size(); i++) { if(freq.get(0) != freq.get(i)) return -1; } return temp.size();}// code to generate all subarrays in n^2static void generateSubArrays(int arr[], int start, int end, int len){ if(end == len) return; else if(start > end) generateSubArrays(arr, 0, end + 1, len); else{ ans = Math.max(ans, checkFreq(arr, start, end)); generateSubArrays(arr, start + 1, end, len); }}// Driver Codepublic static void main(String args[]){ int arr[] = { 1, 10, 5, 4, 4, 4, 10 }; int n = arr.length; generateSubArrays(arr,0,0,n); System.out.println(ans);}}// This code is contributed by shinjanpatra |
Python3
# Python code for the approach# global variable to store the answerfrom pickle import GLOBALans = 1# function to check equal for all equal frequenciesdef checkFreq(arr, r, l): i, count = 1, 1 # vector to store subarray temp = [] # vector to store all frequencies of this subarray freq = [] freq.clear() temp.clear() # insert all subarray elements for i in range(r, l + 1): temp.append(arr[i]) temp.sort() # counting equal consecutive elements to store frequencies for i in range(len(temp) - 1): if(temp[i] == temp[i + 1]): count += 1 else: freq.append(count) count = 1 # checking for all equal elements for i in range(1, len(freq)): if(freq[0] != freq[i]): return -1 return len(temp)# code to generate all subarrays in n^2def generateSubArrays(arr, start, end, Len): global ans if(end == Len): return elif(start > end): generateSubArrays(arr, 0, end + 1, Len) else: ans = max(ans,checkFreq(arr, start, end)) generateSubArrays(arr, start + 1, end, Len) # drivers codearr = [ 1, 10, 5, 4, 4, 4, 10 ]n = len(arr)generateSubArrays(arr, 0, 0, n)print(ans)# This code is contributed by shinjanpatra |
C#
using System;using System.Collections.Generic;public static class GFG { // global variable to store the answer public static int ans = 1; // function to check equal for all equal frequencies public static int checkFreq(int[] arr, int r, int l) { int i, count = 1; // List to store subarray List<int> temp = new List<int>(); // List to store all frequencies of this subarray List<int> freq = new List<int>(); // insert all subarray elements for (i = r; i <= l; i++) temp.Add(arr[i]); temp.Sort(); // counting equal consecutive elements to store // frequencies for (i = 0; i < temp.Count - 1; i++) { if (temp[i] == temp[i + 1]) count++; else { freq.Add(count); count = 1; } } // checking for all equal elements for (i = 1; i < freq.Count; i++) { if (freq[0] != freq[i]) return -1; } return temp.Count; } // code to generate all subarrays in n^2 public static void generateSubArrays(int[] arr, int start, int end, int len) { if (end == len) return; else if (start > end) generateSubArrays(arr, 0, end + 1, len); else { ans = Math.Max(ans, checkFreq(arr, start, end)); generateSubArrays(arr, start + 1, end, len); } } static public void Main() { int[] arr = { 1, 10, 5, 4, 4, 4, 10 }; int n = arr.Length; generateSubArrays(arr, 0, 0, n); Console.WriteLine(ans); }}// This code is contributed by akashish__ |
Javascript
<script>// JavaScript code for the same approach//global variable to store the answerlet ans=1;//function to check equal for all equal frequenciesfunction checkFreq(arr,r,l){ let i,count=1; //vector to store subarray let temp = []; //vector to store all frequencies of this subarray let freq = []; //insert all subarray elements for(i=r;i<=l;i++) temp.push(arr[i]); temp.sort(); //counting equal consecutive elements to store frequencies for(i=0;i<temp.length;i++) { if(temp[i]==temp[i+1]) count++; else{ freq.push(count); count=1; } } //checking for all equal elements for(i=1;i<freq.length;i++) { if(freq[0]!=freq[i]) return -1; } return temp.length;}//code to generate all subarrays in n^2function generateSubArrays(arr,start,end,len){ if(end==len) return; else if(start>end) generateSubArrays(arr,0,end+1,len); else{ ans=Math.max(ans,checkFreq(arr,start,end)); generateSubArrays(arr,start+1,end,len); }}//drivers codelet arr = [ 1, 10, 5, 4, 4, 4, 10 ];let n = arr.length;generateSubArrays(arr,0,0,n);console.log(ans);// code is contributed by shinjanpatra</script> |
Output:
4
Time Complexity: O(n^3 log n)
Auxiliary Space: O(n)
Efficient solution: Another efficient way is to store frequencies of all elements in a map consecutively and check its frequency each time with starting of the map.
C++
#include <bits/stdc++.h>using namespace std;int longestSubArray(int a[],int n){ int i; //minimum subarray will always be 1int ans = 1;for(int i = 0; i < n; i++) { //map to contain all occurrencesmap < int, int > mp;for(int j = i; j < n; j++) { //storing frequencies at key a[j]mp[a[j]] = mp[a[j]] + 1;//checker for each subarraysbool ok = true;//count for each frequencyint count = mp.begin() -> second;//traversing current mapfor(map < int, int > :: iterator it = mp.begin(); it!= mp.end(); ++it) {if(count != it -> second) {ok = false;break;}}if (ok) { //storing maximum valueans = max(ans, j - i + 1);}}}return ans;}//drivers codeint main(){ int arr[]={1,2,8,8,4,4}; int n=sizeof(arr)/sizeof(arr[0]); cout<<longestSubArray(arr,n);} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;class GFG { static int longestSubArray(int a[],int n){ int i; // minimum subarray will always be 1 int ans = 1; for(i = 0; i < n; i++) { // map to contain all occurrences TreeMap <Integer, Integer> mp = new TreeMap<>(); for(int j = i; j < n; j++) { // storing frequencies at key a[j] if(mp.containsKey(a[j])){ mp.put(a[j],mp.get(a[j])+1); } else mp.put(a[j], 1); // checker for each subarrays Boolean ok = true; // count for each frequency int count = mp.firstEntry().getValue(); // traversing current map for(Map.Entry mapEl : mp.entrySet()) { if(count != (int)mapEl.getValue()) { ok = false; break; } } if (ok) { // storing maximum value ans = Math.max(ans, j - i + 1); } } } return ans; } /* Driver program to test above function*/ public static void main(String args[]) { // Input int arr[] = {1,2,8,8,4,4}; int n = arr.length; System.out.println(longestSubArray(arr, n)); }}// This code is contributed by shinjanpatra |
Python3
#Python Code#minimum subarray will always be 1def longestSubArray(a,n): ans = 1 for i in range(n): #map to contain all occurrences mp = {} for j in range(i,n): #storing frequencies at key a[j] if a[j] in mp: mp[a[j]] += 1 else: mp[a[j]] = 1 #checker for each subarrays ok = True #count for each frequency count = list(mp.values())[0] #traversing current map for it in mp.values(): if count != it: ok = False break if ok: #storing maximum value ans = max(ans, j - i + 1) return ans#drivers codearr = [1,2,8,8,4,4]n = len(arr)print(longestSubArray(arr,n))# contributed by akashish__ |
C#
// Include namespace systemusing System;using System.Collections.Generic;using System.Linq;public class GFG{ public static int longestSubArray(int[] a, int n) { int i; // minimum subarray will always be 1 var ans = 1; for (i = 0; i < n; i++) { // map to contain all occurrences var mp = new SortedDictionary<int, int>(); for (int j = i; j < n; j++) { // storing frequencies at key a[j] if (mp.ContainsKey(a[j])) { mp[a[j]] = mp[a[j]] + 1; } else { mp[a[j]] = 1; } // checker for each subarrays var ok = true; // count for each frequency var count = mp[mp.Keys.Min()]; // traversing current map foreach (var key in mp.Keys.ToList()) { if (count != (int)mp[key]) { ok = false; break; } } if (ok) { // storing maximum value ans = Math.Max(ans,j - i + 1); } } } return ans; } // Driver program to test above function public static void Main(String[] args) { // Input int[] arr = {1, 2, 8, 8, 4, 4}; var n = arr.Length; Console.WriteLine(GFG.longestSubArray(arr, n)); }}// This code is contributed by aadityaburujwale. |
Javascript
// JavaScript codeconst longestSubArray = (a, n) => { let i; // minimum subarray will always be 1 let ans = 1; for (let i = 0; i < n; i++) { //map to contain all occurrences let mp = {}; for (let j = i; j < n; j++) { // storing frequencies at key a[j] mp[a[j]] = mp[a[j]] + 1 || 1; // checker for each subarrays let ok = true; // count for each frequency let count = Object.values(mp)[0]; // traversing current map for (let it in mp) { if (count !== mp[it]) { ok = false; break; } } if (ok) { // storing maximum value ans = Math.max(ans, j - i + 1); } } } return ans;};// drivers codeconst arr = [1, 2, 8, 8, 4, 4];const n = arr.length;console.log(longestSubArray(arr, n));// This code is contributed by akashish__ |
Output:
4
Time Complexity: O(n^2 )
Auxiliary Space: O(n)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
