Longitud del subarreglo más pequeño con al menos un elemento repetido K veces

Dada una array arr[] de longitud N y un entero K . La tarea es encontrar la longitud mínima del subarreglo tal que al menos un elemento del subarreglo se repita exactamente K veces en ese subarreglo. Si no existe tal subarreglo, imprima -1 .

Ejemplos:

Entrada: arr[] = {1, 2, 1, 2, 1}, K = 2
Salida: 3
Explicación:  Subarreglo [1,2,1], tiene K = 2 ocurrencias de 1

Entrada: arr[] = {2, 2, 2, 3, 4}, K = 3
Salida: 3

Enfoque: en este problema, observe que la longitud más pequeña se logrará cuando tengamos exactamente un elemento en el subarreglo que tenga una frecuencia K , lo que significa que el subarreglo se parecerá a [X . . . X] donde X es un elemento de la array arr. Ahora, siga los pasos a continuación para resolver este problema:

1. Cree una array de pares, de modo que el número (es decir , arr[i] ) sea el primer elemento y su índice (es decir, i ) sea el segundo.
2. Ordenar esta array.
3. Ahora, cree una variable mn para almacenar la respuesta e inicialícela con INT_MAX .
4. Ahora, recorra la array desde i = 0 hasta i = (N – K) y en cada iteración:
   • Si el elemento en i y (i+K-1) es igual, haga que mn sea igual al mínimo de mn y la diferencia entre los índices de los siguientes.
5. Devuelve mn como respuesta final.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum length of
// subarray having an element exactly K times
int minLengthKRepetitions(int* arr, int& N,
                          int& K)
{
    pair<int, int> indices[N];
    int mn = INT_MAX, i;
 
    for (i = 0; i < N; i++) {
        indices[i].first = arr[i];
        indices[i].second = i;
    }
 
    sort(indices, indices + N);
    for (i = 0; i <= N - K; i++) {
        if (indices[i].first == indices[i + K - 1].first)
            mn = min(mn, indices[i + K - 1].second
                             - indices[i].second + 1);
    }
 
    return (mn == INT_MAX) ? -1 : mn;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 2, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
     
    cout << minLengthKRepetitions(arr, N, K);
    return 0;
}

// Java code to implement the above approach
import java.util.*;
 
class GFG {
 
  // Function to return the minimum length of
  // subarray having an element exactly K times
  public static int minLengthKRepetitions(int[] arr, int N, int K)
  {
    int[][] indices = new int[N][2] ;
    int mn = Integer.MAX_VALUE, i;
 
    for (i = 0; i < N; i++) {
      indices[i][0] = arr[i];
      indices[i][1] = i;
    }
 
    //Arrays.sort(indices);
    for (i = 0; i <= N - K; i++) {
      if (indices[i][0] == indices[i + K - 1][0])
        mn = Math.min(mn, indices[i + K - 1][1]
                      - indices[i][1] + 1);
    }
 
    return (mn == Integer.MAX_VALUE) ? -1 : mn;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    int[] arr = { 1, 2, 2, 2, 1 };
    int N = arr.length;
    int K = 3;
 
    System.out.println(minLengthKRepetitions(arr, N, K));
  }
}
 
// This code is contributed by Shubham Singh

# Python program for the above approach
 
# Function to return the minimum length of
# subarray having an element exactly K times
def minLengthKRepetitions(arr, N, K):
     
    indices = [[0,0] for i in range(N)]
    mn = 2**32
     
    for i in range(N):
        indices[i][0] = arr[i]
        indices[i][1] = i
     
    indices.sort()
    for i in range(N - K + 1):
        if (indices[i][0] == indices[i + K - 1][0]):
            mn = min(mn, indices[i + K - 1][1] - indices[i][1] + 1)
             
    return -1 if(mn == 2**32) else mn
 
# Driver code
arr = [1, 2, 2, 2, 1]
N = len(arr)
K = 3
 
print(minLengthKRepetitions(arr, N, K))
 
# This code is contributed by Shubham Singh

// C# code to implement the above approach
using System;
public class GFG
{
 
  // Function to return the minimum length of
  // subarray having an element exactly K times
  public static int minLengthKRepetitions(int[] arr, int N, int K)
  {
    int[,] indices = new int[N,2] ;
    int mn = Int32.MaxValue, i;
 
    for (i = 0; i < N; i++) {
      indices[i, 0] = arr[i];
      indices[i, 1] = i;
    }
 
    //Arrays.sort(indices);
    for (i = 0; i <= N - K; i++) {
      if (indices[i,0] == indices[i + K - 1,0])
        mn = Math.Min(mn, indices[i + K - 1,1]
                      - indices[i,1] + 1);
    }
 
    return (mn == Int32.MaxValue) ? -1 : mn;
  }
 
  // Driver code
  static public void Main ()
  {
    int[] arr = { 1, 2, 2, 2, 1 };
    int N = arr.Length;
    int K = 3;
 
    Console.Write(minLengthKRepetitions(arr, N, K));
  }
}
 
// This code is contributed by Shubham Singh

<script>
       // JavaScript code for the above approach
 
 
       // Function to return the minimum length of
       // subarray having an element exactly K times
       function minLengthKRepetitions(arr, N,
           K) {
           let indices = [];
           let mn = Number.MAX_VALUE, i;
 
           for (i = 0; i < N; i++) {
               indices.push({ first: arr[i], second: i })
           }
 
           indices.sort(function (a, b) { return a.first - b.first; });
           for (i = 0; i <= N - K; i++) {
               if (indices[i].first == indices[i + K - 1].first)
                   mn = Math.min(mn, indices[i + K - 1].second
                       - indices[i].second + 1);
           }
 
           return (mn == Number.MAX_VALUE) ? -1 : mn;
       }
 
       // Driver code
 
       let arr = [1, 2, 2, 2, 1];
       let N = arr.length;
       let K = 3;
 
       document.write(minLengthKRepetitions(arr, N, K));
 
 // This code is contributed by Potta Lokesh
   </script>

3

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)