Longitud mínima del subarreglo en un arreglo ternario dado que tiene 0 como elemento mayoritario

Dada una array de enteros arr[] de tamaño n con solo tres tipos de enteros 0, 1 y 2 . Encuentre la longitud mínima del subarreglo del arreglo arr[] de longitud >=2, tal que tenga una frecuencia de 0 mayor que 1 y 2 . Si no se encuentra, imprima -1 . 

Entrada: arr[] = {2, 0, 2, 0, 1, 2, 2, 2}
Salida: 3
Explicación: {0, 2, 0} del índice [2, 4] es el subarreglo con frecuencias de 0 mayores frecuencias de 1 y 2.

Entrada: arr[] = {2, 2, 2, 2}
Salida: -1 

Enfoque ingenuo: este problema se puede resolver revisando cada subarreglo y verificando las frecuencias de 0, 1 y 2 y verificando si la frecuencia de 0 es mayor que 2 y 1 y luego almacenando la longitud mínima del subarreglo como la respuesta.

Complejidad temporal: O(n*n)
Espacio auxiliar: O(1)

Enfoque eficiente: dado que solo hay 3 tipos de enteros, los posibles subarreglos de longitud > = 2 que satisfacen la condición anterior serían 

{0, 0}, {0, 1, 0}, {0, 2, 0}, {0, 1, 2, 0}, {0, 2, 1, 0}, {0, 0, 0, 1 , 1, 2, 2}, ….

La longitud mínima máxima posible del subarreglo sería 7 . Cualquier otro subarreglo que satisfaga la condición anterior con una longitud > 7 contendría cualquiera de los subarreglos anteriores, por lo que la longitud máxima posible del subarreglo que satisface la condición anterior es 7.

 Siga estos pasos para resolver este problema:

• Inicialice una variable min_length como INT_MAX
• Iterar en el rango [0, n) usando la variable i y realizar las siguientes tareas:
  • Inicialice un recuento de array [] con frecuencias iniciales 0
  • Incremente la frecuencia de arr[i] usando count[arr[i]]++.
  • Iterar en el rango [i+1, min(n, i+7)) usando la variable j y realizar las siguientes tareas:
    • Incremente la frecuencia de arr[j] usando count[arr[j]]++ de cada subarreglo de tamaño <=7 .
    • Si el conteo[0] es mayor que el conteo[1] y el conteo[2] y si min_length > j-i+1 , entonces asigne min_length = j-i+1
• Si min_length es igual a INT_MAX devuelve -1.
• De lo contrario, imprima min_length como respuesta.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// subarray length with most 0's
int minLength(vector<int> arr)
{
    int min_len = INT_MAX;
    int n = arr.size();
 
    // Traverse the array to check
    // the required condition
    for (int i = 0; i < n; i++) {
 
        // Initialize a vector count
        // to store the frequencies
        int count[3] = { 0 };
        count[arr[i]]++;
 
        // Check all subarrays of length
        // <=7 and count the frequencies
        for (int j = i + 1; j < min(n, i + 7); j++) {
            count[arr[j]]++;
 
            // If the frequency of 0's is
            // greater than both 1's and 2's
            // then take length of minimum subarray
            if (count[0] > count[1]
                && count[0] > count[2])
                min_len = min(min_len, j - i + 1);
        }
    }
 
    // If min_len == INT_MAX we have no subarray
    // satisfying the condition return -1;
    if (min_len == INT_MAX)
        min_len = -1;
 
    return min_len;
}
 
// Driver Code
int main()
{
 
    // Initializing list of nums
    vector<int> arr = { 2, 0, 2, 0, 1, 2, 2, 2 };
 
    // Call the function and print the answer
    cout << (minLength(arr));
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find the minimum
    // subarray length with most 0's
    static int minLength(ArrayList arr)
    {
        int min_len = Integer.MAX_VALUE;
        int n = arr.size();
 
        // Traverse the array to check
        // the required condition
        for (int i = 0; i < n; i++) {
 
            // Initialize a vector count
            // to store the frequencies
            int[] count = new int[3];
            for (int j = 0; j < 3; j++) {
                count[j] = 0;
            }
 
            int x = (int)arr.get(i);
            count[x]++;
 
            // Check all subarrays of length
            // <=7 and count the frequencies
            for (int j = i + 1; j < Math.min(n, i + 7);
                 j++) {
                int y = (int)arr.get(j);
                count[y]++;
 
                // If the frequency of 0's is
                // greater than both 1's and 2's
                // then take length of minimum subarray
                if (count[0] > count[1]
                    && count[0] > count[2])
                    min_len = Math.min(min_len, j - i + 1);
            }
        }
 
        // If min_len == INT_MAX we have no subarray
        // satisfying the condition return -1;
        if (min_len == Integer.MAX_VALUE)
            min_len = -1;
 
        return min_len;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        ArrayList<Integer> arr = new ArrayList<Integer>();
 
        arr.add(2);
        arr.add(0);
        arr.add(2);
        arr.add(0);
        arr.add(1);
        arr.add(2);
        arr.add(2);
        arr.add(2);
 
        // Count of isograms in string array arr[]
        System.out.println(minLength(arr));
    }
}
 
// This code is contributed by ukasp.

# python code for the above approach
INT_MAX = 2147483647
 
# Function to find the minimum
# subarray length with most 0's
def minLength(arr):
 
    min_len = INT_MAX
    n = len(arr)
 
    # Traverse the array to check
    # the required condition
    for i in range(0, n):
 
        # Initialize a vector count
        # to store the frequencies
        count = [0, 0, 0]
        count[arr[i]] += 1
 
        # Check all subarrays of length
        # <=7 and count the frequencies
        for j in range(i+1, min(n, i+7)):
            count[arr[j]] += 1
 
            # If the frequency of 0's is
            # greater than both 1's and 2's
            # then take length of minimum subarray
            if (count[0] > count[1] and count[0] > count[2]):
                min_len = min(min_len, j - i + 1)
 
    # If min_len == INT_MAX we have no subarray
    # satisfying the condition return -1;
    if (min_len == INT_MAX):
        min_len = -1
 
    return min_len
 
# Driver Code
if __name__ == "__main__":
 
    # Initializing list of nums
    arr = [2, 0, 2, 0, 1, 2, 2, 2]
 
    # Call the function and print the answer
    print(minLength(arr))
 
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections;
 
class GFG{
 
// Function to find the minimum
// subarray length with most 0's
static int minLength(ArrayList arr)
{
    int min_len = Int32.MaxValue;
    int n = arr.Count;
 
    // Traverse the array to check
    // the required condition
    for (int i = 0; i < n; i++) {
 
        // Initialize a vector count
        // to store the frequencies
        int []count = new int[3];
        for(int j = 0; j < 3; j++) {
            count[j] = 0;
        }
         
        int x = (int)arr[i];
        count[x]++;
 
        // Check all subarrays of length
        // <=7 and count the frequencies
        for (int j = i + 1; j < Math.Min(n, i + 7); j++) {
          int y = (int)arr[j];
            count[y]++;
 
            // If the frequency of 0's is
            // greater than both 1's and 2's
            // then take length of minimum subarray
            if (count[0] > count[1]
                && count[0] > count[2])
                min_len =   Math.Min(min_len, j - i + 1);
        }
    }
 
    // If min_len == INT_MAX we have no subarray
    // satisfying the condition return -1;
    if (min_len == Int32.MaxValue)
        min_len = -1;
 
    return min_len;
}
 
// Driver Code
public static void Main()
{
    ArrayList arr = new ArrayList();
     
    arr.Add(2);
    arr.Add(0);
    arr.Add(2);
    arr.Add(0);
    arr.Add(1);
    arr.Add(2);
    arr.Add(2);
    arr.Add(2);
 
    // Count of isograms in string array arr[]
    Console.WriteLine(minLength(arr));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code for the above approach
    const INT_MAX = 2147483647
 
    // Function to find the minimum
    // subarray length with most 0's
    const minLength = (arr) => {
        let min_len = INT_MAX;
        let n = arr.length;
 
        // Traverse the array to check
        // the required condition
        for (let i = 0; i < n; i++) {
 
            // Initialize a vector count
            // to store the frequencies
            let count = [0, 0, 0];
            count[arr[i]]++;
 
            // Check all subarrays of length
            // <=7 and count the frequencies
            for (let j = i + 1; j < Math.min(n, i + 7); j++) {
                count[arr[j]]++;
 
                // If the frequency of 0's is
                // greater than both 1's and 2's
                // then take length of minimum subarray
                if (count[0] > count[1]
                    && count[0] > count[2])
                    min_len = Math.min(min_len, j - i + 1);
            }
        }
 
        // If min_len == INT_MAX we have no subarray
        // satisfying the condition return -1;
        if (min_len == INT_MAX)
            min_len = -1;
 
        return min_len;
    }
 
    // Driver Code
 
    // Initializing list of nums
    let arr = [2, 0, 2, 0, 1, 2, 2, 2];
 
    // Call the function and print the answer
    document.write(minLength(arr));
 
    // This code is contributed by rakeshsahni
 
</script>

3

Complejidad temporal: O(n)
Espacio auxiliar: O(1)