Elemento común mínimo en subarreglos de todas las longitudes posibles

Dada una array arr[] que consta de N enteros del rango [1, N] ( repetición permitida ), la tarea es encontrar el elemento común mínimo para cada longitud de subarreglo posible. Si no existe tal elemento para una longitud particular del subarreglo, imprima -1 .

Ejemplos:

Entrada: arr[] = {1, 3, 4, 5, 6, 7}
Salida: -1 -1 -1 4 3 1
Explicación: 
K = 1: No existe ningún elemento común. Por lo tanto, imprima -1. 
K = 2: No existe ningún elemento común. Por lo tanto, imprima -1. 
K = 3: No existe ningún elemento común. Por lo tanto, imprima -1. 
K = 4: dado que 4 es común en todos los subarreglos de tamaño 4, imprima 4. 
K = 5: dado que 3 y 4 son comunes en todos los subarreglos de tamaño 5, imprima 3 porque es el mínimo. 
K = 6: imprime 1 ya que es el elemento mínimo en la array.
 

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

Enfoque: siga los pasos a continuación para resolver el problema: 

• Recorra la array y almacene la última aparición de cada elemento en un mapa .
• Inicialice una array temp[] y almacene en ella, para cada valor, la distancia máxima entre cualquier par de repeticiones consecutivas de la misma en la array.
• Una vez que se complete el paso anterior, actualice temp[] comparando temp[i] con la distancia de la última aparición de i desde el final de la array.
• Ahora, almacene el elemento de comentario mínimo para todos los subarreglos de longitud 1 a N uno por uno e imprímalos.

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

// C++ Program to implement the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum distance
// between every two element
void max_distance(int a[], int temp[], int n)
{
    // Stores index of last occurrence
    // of each array element
    map<int, int> mp;
 
    // Initialize temp[] with -1
    for (int i = 1; i <= n; i++) {
        temp[i] = -1;
    }
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If array element has
        // not occurred previously
        if (mp.find(a[i]) == mp.end())
 
            // Update index in temp
            temp[a[i]] = i + 1;
 
        // Otherwise
        else
 
            // Compare temp[a[i]] with distance
            // from its previous occurrence and
            // store the maximum
            temp[a[i]] = max(temp[a[i]],
                             i - mp[a[i]]);
 
        mp[a[i]] = i;
    }
 
    for (int i = 1; i <= n; i++) {
 
        // Compare temp[i] with distance
        // of its last occurrence from the end
        // of the array and store the maximum
        if (temp[i] != -1)
            temp[i] = max(temp[i], n - mp[i]);
    }
}
 
// Function to find the minimum common
// element in subarrays of all possible lengths
void min_comm_ele(int a[], int ans[],
                  int temp[], int n)
{
    // Function call to find a the maximum
    // distance between every pair of repetition
    max_distance(a, temp, n);
 
    // Initialize ans[] to -1
    for (int i = 1; i <= n; i++) {
        ans[i] = -1;
    }
 
    for (int i = 1; i <= n; i++) {
 
        // Check if subarray of length
        // temp[i] contains i as one
        // of the common elements
        if (ans[temp[i]] == -1)
            ans[temp[i]] = i;
    }
 
    for (int i = 1; i <= n; i++) {
 
        // Find the minimum of all
        // common elements
        if (i > 1 && ans[i - 1] != -1) {
 
            if (ans[i] == -1)
                ans[i] = ans[i - 1];
            else
                ans[i] = min(ans[i],
                             ans[i - 1]);
        }
 
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 6;
    int a[] = { 1, 3, 4, 5, 6, 7 };
    int temp[100], ans[100];
    min_comm_ele(a, ans, temp, N);
 
    return 0;
}

// Java program to implement the
// above approach
import java.util.*;
 
class GFG{
    
// Function to find maximum distance
// between every two element
static void max_distance(int a[], int temp[], int n)
{
     
    // Stores index of last occurrence
    // of each array element
    Map<Integer,
        Integer> mp = new HashMap<Integer,
                                  Integer>();
 
    // Initialize temp[] with -1
    for(int i = 1; i <= n; i++)
    {
        temp[i] = -1;
    }
 
    // Traverse the array
    for(int i = 0; i < n; i++)
    {
         
        // If array element has
        // not occurred previously
        if (mp.get(a[i]) == null)
         
            // Update index in temp
            temp[a[i]] = i + 1;
 
        // Otherwise
        else
 
            // Compare temp[a[i]] with distance
            // from its previous occurrence and
            // store the maximum
            temp[a[i]] = Math.max(temp[a[i]],
                   i - mp.getOrDefault(a[i], 0));
 
        mp.put(a[i], i);
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Compare temp[i] with distance
        // of its last occurrence from the end
        // of the array and store the maximum
        if (temp[i] != -1)
            temp[i] = Math.max(temp[i],
                               n - mp.getOrDefault(i, 0));
    }
}
 
// Function to find the minimum common
// element in subarrays of all possible lengths
static void min_comm_ele(int a[], int ans[],
                         int temp[], int n)
{
     
    // Function call to find a the maximum
    // distance between every pair of repetition
    max_distance(a, temp, n);
 
    // Initialize ans[] to -1
    for(int i = 1; i <= n; i++)
    {
        ans[i] = -1;
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Check if subarray of length
        // temp[i] contains i as one
        // of the common elements
        if (temp[i] >= 0 && ans[temp[i]] == -1)
            ans[temp[i]] = i;
    }
 
    for(int i = 1; i <= n; i++)
    {
         
        // Find the minimum of all
        // common elements
        if (i > 1 && ans[i - 1] != -1)
        {
            if (ans[i] == -1)
                ans[i] = ans[i - 1];
            else
                ans[i] = Math.min(ans[i],
                                  ans[i - 1]);
        }
        System.out.print(ans[i] + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 6;
    int a[] = { 1, 3, 4, 5, 6, 7 };
     
    int []temp = new int[100];
    Arrays.fill(temp, 0);
     
    int []ans = new int[100];
    Arrays.fill(ans, 0);
     
    min_comm_ele(a, ans, temp, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

# Python3 Program to implement
# the above approach
 
# Function to find maximum
# distance between every
# two element
def max_distance(a, temp, n):
 
    # Stores index of last
    # occurrence of each
    # array element
    mp = {}
 
    # Initialize temp[]
    # with -1
    for i in range(1, n + 1):
        temp[i] = -1
 
    # Traverse the array
    for i in range(n):
 
        # If array element has
        # not occurred previously
        if (a[i] not in mp):
 
            # Update index in temp
            temp[a[i]] = i + 1
 
        # Otherwise
        else:
 
            # Compare temp[a[i]] with
            # distance from its previous
            # occurrence and store the maximum
            temp[a[i]] = max(temp[a[i]],
                             i - mp[a[i]])
 
        mp[a[i]] = i
 
    for i in range(1, n + 1):
 
        # Compare temp[i] with
        # distance of its last
        # occurrence from the end
        # of the array and store
        # the maximum
        if (temp[i] != -1):
            temp[i] = max(temp[i],
                          n - mp[i])
 
# Function to find the minimum
# common element in subarrays
# of all possible lengths
def min_comm_ele(a, ans,
                 temp, n):
 
    # Function call to find
    # a the maximum distance
    # between every pair of
    # repetition
    max_distance(a, temp, n)
 
    # Initialize ans[] to -1
    for i in range(1, n + 1):
        ans[i] = -1
 
    for i in range(1, n + 1):
 
        # Check if subarray of length
        # temp[i] contains i as one
        # of the common elements
        if (ans[temp[i]] == -1):
            ans[temp[i]] = i
 
    for i in range(1, n + 1):
 
        # Find the minimum of all
        # common elements
        if (i > 1 and
            ans[i - 1] != -1):
 
            if (ans[i] == -1):
                ans[i] = ans[i - 1]
            else:
                ans[i] = min(ans[i],
                             ans[i - 1])
 
        print(ans[i], end = " ")
 
# Driver Code
if __name__ == "__main__":
 
    N = 6
    a = [1, 3, 4, 5, 6, 7]
    temp = [0] * 100
    ans = [0] * 100
    min_comm_ele(a, ans,
                 temp, N)
 
# This code is contributed by Chitranayal

// C# program to implement the
// above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to find maximum distance
    // between every two element
    static void max_distance(int[] a, int[] temp, int n)
    {
          
        // Stores index of last occurrence
        // of each array element
        Dictionary<int, int> mp = new Dictionary<int, int>(); 
      
        // Initialize temp[] with -1
        for(int i = 1; i <= n; i++)
        {
            temp[i] = -1;
        }
      
        // Traverse the array
        for(int i = 0; i < n; i++)
        {
              
            // If array element has
            // not occurred previously
            if (!mp.ContainsKey(a[i]))
              
                // Update index in temp
                temp[a[i]] = i + 1;
      
            // Otherwise
            else
      
                // Compare temp[a[i]] with distance
                // from its previous occurrence and
                // store the maximum
                temp[a[i]] = Math.Max(temp[a[i]], i - mp[a[i]]);
             
            if(mp.ContainsKey(a[i]))
            {
                mp[a[i]] = i;
            }
            else{
                mp.Add(a[i], i);
            }
        }
      
        for(int i = 1; i <= n; i++)
        {
              
            // Compare temp[i] with distance
            // of its last occurrence from the end
            // of the array and store the maximum
            if (temp[i] != -1)
            {
                if(mp.ContainsKey(i))
                {
                    temp[i] = Math.Max(temp[i], n - mp[i]);
                }
                else{
                    temp[i] = Math.Max(temp[i], n);
                }
            }
        }
    }
      
    // Function to find the minimum common
    // element in subarrays of all possible lengths
    static void min_comm_ele(int[] a, int[] ans,
                             int[] temp, int n)
    {
          
        // Function call to find a the maximum
        // distance between every pair of repetition
        max_distance(a, temp, n);
      
        // Initialize ans[] to -1
        for(int i = 1; i <= n; i++)
        {
            ans[i] = -1;
        }
      
        for(int i = 1; i <= n; i++)
        {
              
            // Check if subarray of length
            // temp[i] contains i as one
            // of the common elements
            if (temp[i] >= 0 && ans[temp[i]] == -1)
                ans[temp[i]] = i;
        }
      
        for(int i = 1; i <= n; i++)
        {
              
            // Find the minimum of all
            // common elements
            if (i > 1 && ans[i - 1] != -1)
            {
                if (ans[i] == -1)
                    ans[i] = ans[i - 1];
                else
                    ans[i] = Math.Min(ans[i],
                                      ans[i - 1]);
            }
            Console.Write(ans[i] + " ");
        }
    }
 
  // Driver code
  static void Main()
  {
       
        int N = 6;
        int[] a = { 1, 3, 4, 5, 6, 7 };
          
        int[] temp = new int[100];
        Array.Fill(temp, 0);
          
        int[] ans = new int[100];
        Array.Fill(ans, 0);
          
        min_comm_ele(a, ans, temp, N);
  }
}
 
// This code is contributed by divyeshrabadiya07

<script>
  
// JavaScript Program to implement the
// above approach
 
// Function to find maximum distance
// between every two element
function max_distance(a, temp, n)
{
    // Stores index of last occurrence
    // of each array element
    var mp = new Map();
 
    // Initialize temp[] with -1
    for (var i = 1; i <= n; i++) {
        temp[i] = -1;
    }
 
    // Traverse the array
    for (var i = 0; i < n; i++) {
 
        // If array element has
        // not occurred previously
        if (!mp.has(a[i]))
 
            // Update index in temp
            temp[a[i]] = i + 1;
 
        // Otherwise
        else
 
            // Compare temp[a[i]] with distance
            // from its previous occurrence and
            // store the maximum
            temp[a[i]] = Math.max(temp[a[i]],
                             i - mp[a[i]]);
 
        mp.set(a[i], i);
    }
 
    for (var i = 1; i <= n; i++) {
 
        // Compare temp[i] with distance
        // of its last occurrence from the end
        // of the array and store the maximum
        if (temp[i] != -1)
            temp[i] = Math.max(temp[i], n - mp.get(i));
    }
}
 
// Function to find the minimum common
// element in subarrays of all possible lengths
function min_comm_ele(a, ans, temp, n)
{
    // Function call to find a the maximum
    // distance between every pair of repetition
    max_distance(a, temp, n);
 
    // Initialize ans[] to -1
    for (var i = 1; i <= n; i++) {
        ans[i] = -1;
    }
 
    for (var i = 1; i <= n; i++) {
 
        // Check if subarray of length
        // temp[i] contains i as one
        // of the common elements
        if (ans[temp[i]] == -1)
            ans[temp[i]] = i;
    }
 
    for (var i = 1; i <= n; i++) {
 
        // Find the minimum of all
        // common elements
        if (i > 1 && ans[i - 1] != -1) {
 
            if (ans[i] == -1)
                ans[i] = ans[i - 1];
            else
                ans[i] = Math.min(ans[i],
                             ans[i - 1]);
        }
 
        document.write( ans[i] + " ");
    }
}
 
// Driver Code
var N = 6;
var a = [1, 3, 4, 5, 6, 7];
var temp =  new Array(100), ans = Array(100);
min_comm_ele(a, ans, temp, N);
 
 
</script>

-1 -1 -1 4 3 1

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)