Distancia mínima entre dos elementos iguales en un Array

Dada una array arr , la tarea es encontrar la distancia mínima entre dos elementos iguales en la array. Si no se encuentra dicho elemento, devuelve -1.

Ejemplos:  

Entrada: arr = {1, 2, 3, 2, 1} 
Salida: 2 
Explicación: 
Hay dos pares de valores coincidentes: 1 y 2 en esta array. 
Distancia mínima entre dos 1 = 4 
Distancia mínima entre dos 2 = 2 
Por lo tanto, la distancia mínima entre dos elementos iguales en el arreglo = 2

Entrada: arr = {3, 5, 4, 6, 5, 3} 
Salida: 3 
Explicación: 
Hay dos pares de valores coincidentes: 3 y 5 en esta array. 
Distancia mínima entre dos 3 = 5 
Distancia mínima entre dos 5 = 3 
Por lo tanto, distancia mínima entre dos elementos iguales en el arreglo = 3 
 

Enfoque ingenuo: el enfoque más simple es usar dos bucles for anidados para formar todas y cada una de las combinaciones. Si los elementos son iguales, encuentre la distancia mínima. 
Complejidad temporal: O(N ² )

Enfoque eficiente: un enfoque eficiente para este problema es usar map para almacenar elementos de array como una clave y su índice como los valores . 

A continuación se muestra el algoritmo paso a paso:  

1. Atraviese la array uno por uno .
2. Compruebe si este elemento está en el mapa o no . 
   • Si el mapa no contiene este elemento, insértelo como par (elemento, índice actual) .
   • Si el elemento de la array está presente en el mapa, obtenga el índice anterior de este elemento del mapa.
3. Encuentre la diferencia entre el índice anterior y el índice actual
4. Compara cada diferencia y encuentra la distancia mínima .
5. Si no se encuentra dicho elemento, devuelve -1.

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

// C++ program to find the minimum distance
// between two occurrences of the same element
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// distance between the same elements
int minimumDistance(int a[], int n)
{
 
    // Create a HashMap to
    // store (key, values) pair.
    map<int,int> hmap;
 
    int minDistance = INT_MAX;
 
    // Initialize previousIndex
    // and currentIndex as 0
    int previousIndex = 0, currentIndex = 0;
 
    // Traverse the array and
    // find the minimum distance
    // between the same elements with map
 
    for (int i = 0; i < n; i++) {
 
        if (hmap.find(a[i])!=hmap.end()) {
            currentIndex = i;
 
            // Fetch the previous index from map.
            previousIndex = hmap[a[i]];
 
            // Find the minimum distance.
            minDistance = min((currentIndex -
                        previousIndex),minDistance);
        }
 
        // Update the map.
        hmap[a[i]] = i;
    }
 
    // return minimum distance,
    // if no such elements found, return -1
    return (minDistance == INT_MAX ? -1 : minDistance);
}
 
// Driver code
int main()
{
 
    // Test Case 1:
    int a1[] = { 1, 2, 3, 2, 1 };
    int n = sizeof(a1)/sizeof(a1[0]);
 
    cout << minimumDistance(a1, n) << endl;
 
    // Test Case 2:
    int a2[] = { 3, 5, 4, 6, 5, 3 };
    n = sizeof(a2)/sizeof(a2[0]);
    cout << minimumDistance(a2, n) << endl;
 
    // Test Case 3:
    int a3[] = { 1, 2, 1, 4, 1 };
    n = sizeof(a3)/sizeof(a3[0]);
 
    cout << minimumDistance(a3, n) << endl;
}
 
// This code is contributed by Sanjit_Prasad

// Java program to find the minimum distance
// between two occurrences of the same element
 
import java.util.*;
import java.math.*;
 
class GFG {
 
    // Function to find the minimum
    // distance between the same elements
    static int minimumDistance(int[] a)
    {
 
        // Create a HashMap to
        // store (key, values) pair.
        HashMap<Integer, Integer> hmap
            = new HashMap<>();
        int minDistance = Integer.MAX_VALUE;
 
        // Initialize previousIndex
        // and currentIndex as 0
        int previousIndex = 0, currentIndex = 0;
 
        // Traverse the array and
        // find the minimum distance
        // between the same elements with map
        for (int i = 0; i < a.length; i++) {
 
            if (hmap.containsKey(a[i])) {
                currentIndex = i;
 
                // Fetch the previous index from map.
                previousIndex = hmap.get(a[i]);
 
                // Find the minimum distance.
                minDistance
                    = Math.min(
                        (currentIndex - previousIndex),
                        minDistance);
            }
 
            // Update the map.
            hmap.put(a[i], i);
        }
 
        // return minimum distance,
        // if no such elements found, return -1
        return (
            minDistance == Integer.MAX_VALUE
                ? -1
                : minDistance);
    }
 
    // Driver code
    public static void main(String args[])
    {
 
        // Test Case 1:
        int a1[] = { 1, 2, 3, 2, 1 };
        System.out.println(minimumDistance(a1));
 
        // Test Case 2:
        int a2[] = { 3, 5, 4, 6, 5, 3 };
        System.out.println(minimumDistance(a2));
 
        // Test Case 3:
        int a3[] = { 1, 2, 1, 4, 1 };
        System.out.println(minimumDistance(a3));
    }
}

# Python3 program to find the minimum distance
# between two occurrences of the same element
 
# Function to find the minimum
# distance between the same elements
def minimumDistance(a):
 
    # Create a HashMap to
    # store (key, values) pair.
    hmap = dict()
    minDistance = 10**9
 
    # Initialize previousIndex
    # and currentIndex as 0
    previousIndex = 0
    currentIndex = 0
 
    # Traverse the array and
    # find the minimum distance
    # between the same elements with map
    for i in range(len(a)):
 
        if a[i] in hmap:
            currentIndex = i
 
            # Fetch the previous index from map.
            previousIndex = hmap[a[i]]
 
            # Find the minimum distance.
            minDistance = min((currentIndex -
                        previousIndex), minDistance)
 
        # Update the map.
        hmap[a[i]] = i
 
    # return minimum distance,
    # if no such elements found, return -1
    if minDistance == 10**9:
        return -1
    return minDistance
 
# Driver code
if __name__ == '__main__':
     
    # Test Case 1:
    a1 = [1, 2, 3, 2, 1 ]
    print(minimumDistance(a1))
 
    # Test Case 2:
    a2 = [3, 5, 4, 6, 5,3]
    print(minimumDistance(a2))
 
    # Test Case 3:
    a3 = [1, 2, 1, 4, 1 ]
    print(minimumDistance(a3))
     
# This code is contributed by mohit kumar 29   

// C# program to find the minimum distance
// between two occurrences of the same element
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find the minimum
// distance between the same elements
static int minimumDistance(int[] a)
{
     
    // Create a HashMap to
    // store (key, values) pair.
    Dictionary<int,
               int> hmap = new Dictionary<int,
                                          int>();
    int minDistance = Int32.MaxValue;
 
    // Initialize previousIndex
    // and currentIndex as 0
    int previousIndex = 0, currentIndex = 0;
 
    // Traverse the array and
    // find the minimum distance
    // between the same elements with map
    for(int i = 0; i < a.Length; i++)
    {
        if (hmap.ContainsKey(a[i]))
        {
            currentIndex = i;
             
            // Fetch the previous index from map.
            previousIndex = hmap[a[i]];
 
            // Find the minimum distance.
            minDistance = Math.Min((currentIndex -
                                    previousIndex),
                                    minDistance);
        }
 
        // Update the map.
        if (!hmap.ContainsKey(a[i]))
            hmap.Add(a[i], i);
        else
            hmap[a[i]] = i;
    }
 
    // Return minimum distance,
    // if no such elements found, return -1
    return(minDistance == Int32.MaxValue ?
                    -1 : minDistance);
}
 
// Driver code
static public void Main()
{
     
    // Test Case 1:
    int[] a1 = { 1, 2, 3, 2, 1 };
    Console.WriteLine(minimumDistance(a1));
     
    // Test Case 2:
    int[] a2 = { 3, 5, 4, 6, 5, 3 };
    Console.WriteLine(minimumDistance(a2));
     
    // Test Case 3:
    int[] a3 = { 1, 2, 1, 4, 1 };
    Console.WriteLine(minimumDistance(a3));
}
}
 
// This code is contributed by unknown2108

<script>
 
// Javascript program to find the minimum distance
// between two occurrences of the same element
 
// Function to find the minimum
// distance between the same elements
function minimumDistance(a, n)
{
 
    // Create a HashMap to
    // store (key, values) pair.
    var hmap = new Map();
 
    var minDistance = 1000000000;
 
    // Initialize previousIndex
    // and currentIndex as 0
    var previousIndex = 0, currentIndex = 0;
 
    // Traverse the array and
    // find the minimum distance
    // between the same elements with map
 
    for (var i = 0; i < n; i++) {
 
        if (hmap.has(a[i])) {
            currentIndex = i;
 
            // Fetch the previous index from map.
            previousIndex = hmap.get(a[i]);
 
            // Find the minimum distance.
            minDistance = Math.min((currentIndex -
                        previousIndex),minDistance);
        }
 
        // Update the map.
        hmap.set(a[i], i);
    }
 
    // return minimum distance,
    // if no such elements found, return -1
    return (minDistance == 1000000000 ? -1 : minDistance);
}
 
// Driver code
// Test Case 1:
var a1 = [1, 2, 3, 2, 1];
var n = a1.length;
document.write( minimumDistance(a1, n) + "<br>");
 
// Test Case 2:
var a2 = [3, 5, 4, 6, 5, 3];
n = a2.length;
document.write( minimumDistance(a2, n) + "<br>");
 
// Test Case 3:
var a3 = [1, 2, 1, 4, 1];
n = a3.length;
document.write( minimumDistance(a3, n));
 
// This code is contributed by famously.
</script>

2
3
2

Complejidad del tiempo: O(N)