El subarreglo más grande con frecuencia de todos los elementos iguales

Dado un arreglo arr[] de N enteros, la tarea es encontrar el tamaño del subarreglo más grande con la misma frecuencia de todos los elementos.

Ejemplos: 

Entrada: arr[] = {1, 2, 2, 5, 6, 5, 6} 
Salida: 6 
Explicación: 
El subarreglo = {2, 2, 5, 6, 5, 6} tiene una frecuencia de cada elemento igual a 2.

Entrada: arr[] = {1, 1, 1, 1, 1} 
Salida: 5 
Explicación: 
El subarreglo = {1, 1, 1, 1, 1} tiene una frecuencia de cada elemento de 5.

Enfoque: La idea es generar todos los subarreglos posibles y verificar para cada subarreglo si algún subarreglo tiene la frecuencia de todos los elementos o no. A continuación se muestran los pasos:

1. Genere todos los subarreglos posibles.
2. Para cada subarreglo, tome dos mapas , un mapa para almacenar la frecuencia de cada elemento y el segundo mapa almacena el número de elementos con una frecuencia determinada.
3. Si para cualquier subarreglo, el tamaño del segundo mapa se vuelve igual a 1 , eso significa que todos los elementos tienen la misma frecuencia en el subarreglo.
4. Devuelve el tamaño máximo de todos esos subarreglos.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
#include <unordered_map>
using namespace std;
 
// Function to find maximum subarray size
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
        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 Code
int 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 program for the above approach
import 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 program for the above approach
 
# Function to find maximum subarray size
def 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 Call
print(max_subarray_size(N, arr))
 
# This code is contributed by divyeshrabadiya07

// C# program for the above approach
using System;
using System.Collections.Generic;
 
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
        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 Code
static 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

<script>
// JavaScript program for the above approach
 
// Function to find maximum subarray size
function 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 arr
const arr = [ 1, 2, 2, 5, 6, 5, 6 ];
 
const N = arr.length;
 
// Function Call
document.write(max_subarray_size(N, arr));
 
// This code is contributed by shinjanpatra.
</script>

6

Tiempo Complejidad: O(N ² )  
Espacio Auxiliar: O(N)

Enfoque ingenuo: la solución simple es generar todos los subarreglos y verificar si cada elemento tiene la misma frecuencia o no.

#include <bits/stdc++.h>
using namespace std;
 
//global variable to store the answer
int ans=1;
 
//function to check equal for all equal frequencies
int 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^2
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=max(ans,checkFreq(arr,start,end));
        generateSubArrays(arr,start+1,end,len);
    }
}
 
 
//drivers code
int 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;
}

/*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 answer
static int ans = 1;
 
// function to check equal for all equal frequencies
static 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^2
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);
    }
}
 
// Driver Code
public 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

# Python code for the approach
 
# global variable to store the answer
from pickle import GLOBAL
 
ans = 1
 
# function to check equal for all equal frequencies
def 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^2
def 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 code
arr = [ 1, 10, 5, 4, 4, 4, 10 ]
n = len(arr)
generateSubArrays(arr, 0, 0, n)
print(ans)
 
# This code is contributed by shinjanpatra

<script>
 
// JavaScript code for the same approach
 
//global variable to store the answer
let ans=1;
 
//function to check equal for all equal frequencies
function 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^2
function 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 code
 
 
let 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>

Producción:

4

Complejidad del tiempo: O(n^3 log n)

Espacio Auxiliar: O(n)

Solución eficiente: otra forma eficiente es almacenar las frecuencias de todos los elementos en un mapa consecutivamente y verificar su frecuencia cada vez que se inicia el mapa.

#include <bits/stdc++.h>
using namespace std;
 
int longestSubArray(int a[],int n){
    int i;
    //minimum subarray will always be 1
int ans = 1;
 
for(int i = 0; i < n; i++) {
    //map to contain all occurrences
map < 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 subarrays
bool ok = true;
 
//count for each frequency
int count = mp.begin() -> second;
 
//traversing current map
for(map < int, int > :: iterator it = mp.begin(); it!= mp.end(); ++it) {
 
if(count != it -> second) {
ok = false;
break;
}
}
if (ok) {
    //storing maximum value
ans = max(ans, j - i + 1);
}
}
}
return ans;
}
 
//drivers code
int main()
{
    int arr[]={1,2,8,8,4,4};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout<<longestSubArray(arr,n);
}

/*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

Producción:

4

Complejidad del tiempo: O(n^2 )

Espacio Auxiliar: O(n)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array