Distancia mínima entre el elemento máximo y mínimo de un Array dado

Dada una array A[] que consta de N elementos, la tarea es encontrar la distancia mínima entre el elemento mínimo y máximo de la array .
Ejemplos:  

Entrada: arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 8, 2} 
Salida: 3 
Explicación: 
El elemento mínimo (= 1) está presente en los índices {2, 4} 
El elemento máximo (= 8) está presente en los índices {7, 10}. 
La distancia mínima entre una ocurrencia de 1 y 8 es 7 – 4 = 3
Entrada: arr[] = {1, 3, 69} 
Salida: 2 
Explicación: 
El elemento mínimo (= 1) está presente en el índice 0. 
El elemento máximo (= 69) está presente en el índice 2. 
Por lo tanto, la distancia mínima entre ellos es 2. 
 

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es el siguiente:  

• Encuentre los elementos mínimo y máximo de la array.
• Recorra la array y, para cada ocurrencia del elemento máximo, calcule su distancia desde todas las ocurrencias del elemento mínimo en la array y actualice la distancia mínima.
• Después de completar el recorrido de la array, imprima toda la distancia mínima obtenida.

Complejidad de tiempo: O(N ² ) 
Espacio auxiliar: O(1) 
Enfoque eficiente: 
Siga los pasos a continuación para optimizar el enfoque anterior:  

• Recorre la array para encontrar los elementos mínimo y máximo.
• Inicialice dos variables min_index y max_index para almacenar los índices de los elementos mínimo y máximo de la array, respectivamente. Inicializarlos con -1.
• Atraviesa la array. Si en algún momento, tanto min_index como max_index no es igual a -1, es decir, ambos han almacenado un índice válido, calcule allí una diferencia.
• Compare esta diferencia con la distancia mínima (por ejemplo, min_dist ) y actualice min_dist en consecuencia.
• Finalmente, imprima el valor final de min_dist obtenido después del recorrido completo de la array.

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 the minimum
// distance between the minimum
// and the maximum element
int minDistance(int a[], int n)
{
    // Stores the minimum and maximum
    // array element
    int maximum = -1, minimum = INT_MAX;
 
    // Stores the most recently traversed
    // indices of the minimum and the
    // maximum element
    int min_index = -1, max_index = -1;
 
    // Stores the minimum distance
    // between the minimum and the
    // maximum
    int min_dist = n + 1;
 
    // Find the maximum and
    // the minimum element
    // from the given array
    for (int i = 0; i < n; i++) {
 
        if (a[i] > maximum)
            maximum = a[i];
 
        if (a[i] < minimum)
            minimum = a[i];
    }
 
    // Find the minimum distance
    for (int i = 0; i < n; i++) {
 
        // Check if current element
        // is equal to minimum
        if (a[i] == minimum)
            min_index = i;
 
        // Check if current element
        // is equal to maximum
        if (a[i] == maximum)
            max_index = i;
 
        // If both the minimum and the
        // maximum element has
        // occurred at least once
        if (min_index != -1
            && max_index != -1)
 
            // Update the minimum distance
            min_dist
                = min(min_dist,
                      abs(min_index
                          - max_index));
    }
 
    // Return the answer
    return min_dist;
}
 
// Driver Code
int main()
{
    int a[] = { 3, 2, 1, 2, 1, 4,
                5, 8, 6, 7, 8, 2 };
    int n = sizeof a / sizeof a[0];
    cout << minDistance(a, n);
}

// Java Program to implement
// the above approach
import java.util.*;
class GFG {
 
    // Function to find the minimum
    // distance between the minimum
    // and the maximum element
    public static int minDistance(int a[], int n)
    {
 
        // Stores the minimum and maximum
        // array element
        int max = -1, min = Integer.MAX_VALUE;
 
        // Stores the most recently traversed
        // indices of the minimum and the
        // maximum element
        int min_index = -1, max_index = -1;
 
        // Stores the minimum distance
        // between the minimum and the
        // maximum
        int min_dist = n + 1;
 
        // Find the maximum and
        // the minimum element
        // from the given array
        for (int i = 0; i < n; i++) {
            if (a[i] > max)
                max = a[i];
            if (a[i] < min)
                min = a[i];
        }
 
        // Find the minimum distance
        for (int i = 0; i < n; i++) {
 
            // Check if current element
            // is equal to minimum
            if (a[i] == min)
                min_index = i;
 
            // Check if current element
            // is equal to maximum
            if (a[i] == max)
                max_index = i;
 
            // If both the minimum and the
            // maximum element has
            // occurred at least once
            if (min_index != -1
                && max_index != -1)
                min_dist
                    = Math.min(min_dist,
                               Math.abs(min_index
                                        - max_index));
        }
        return min_dist;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 12;
        int a[] = { 3, 2, 1, 2, 1, 4,
                    5, 8, 6, 7, 8, 2 };
        System.out.println(minDistance(a, n));
    }
}

# Python3 Program to implement the
# above approach
import sys
 
# Function to find the minimum
# distance between the minimum
# and the maximum element
def minDistance(a, n):
 
    # Stores the minimum and maximum
    # array element
    maximum = -1
    minimum = sys.maxsize
  
    # Stores the most recently traversed
    # indices of the minimum and the
    # maximum element
    min_index = -1
    max_index = -1
  
    # Stores the minimum distance
    # between the minimum and the
    # maximum
    min_dist = n + 1
  
    # Find the maximum and
    # the minimum element
    # from the given array
    for i in range (n):
        if (a[i] > maximum):
            maximum = a[i]
 
        if (a[i] < minimum):
            minimum = a[i]
  
    # Find the minimum distance
    for i in range (n):
  
        # Check if current element
        # is equal to minimum
        if (a[i] == minimum):
            min_index = i
  
        # Check if current element
        # is equal to maximum
        if (a[i] == maximum):
            max_index = i
  
        # If both the minimum and the
        # maximum element has
        # occurred at least once
        if (min_index != -1 and
            max_index != -1):
  
            # Update the minimum distance
            min_dist = (min(min_dist,
                        abs(min_index -
                            max_index)))
  
    # Return the answer
    return min_dist
  
# Driver Code
if __name__ == "__main__":
 
    a = [3, 2, 1, 2, 1, 4,
         5, 8, 6, 7, 8, 2]
    n = len(a)
    print (minDistance(a, n))
 
# This code is contributed by Chitranayal

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to find the minimum
// distance between the minimum
// and the maximum element
static int minDistance(int []a, int n)
{
     
    // Stores the minimum and maximum
    // array element
    int max = -1, min = Int32.MaxValue;
 
    // Stores the most recently traversed
    // indices of the minimum and the
    // maximum element
    int min_index = -1, max_index = -1;
 
    // Stores the minimum distance
    // between the minimum and the
    // maximum
    int min_dist = n + 1;
 
    // Find the maximum and
    // the minimum element
    // from the given array
    for(int i = 0; i < n; i++)
    {
        if (a[i] > max)
            max = a[i];
        if (a[i] < min)
            min = a[i];
    }
 
    // Find the minimum distance
    for(int i = 0; i < n; i++)
    {
        // Check if current element
        // is equal to minimum
        if (a[i] == min)
            min_index = i;
 
        // Check if current element
        // is equal to maximum
        if (a[i] == max)
            max_index = i;
 
        // If both the minimum and the
        // maximum element has
        // occurred at least once
        if (min_index != -1 && max_index != -1)
            min_dist = Math.Min(min_dist,
                                Math.Abs(
                                min_index -
                                max_index));
    }
    return min_dist;
}
 
// Driver Code
public static void Main()
{
    int n = 12;
    int []a = { 3, 2, 1, 2, 1, 4,
                5, 8, 6, 7, 8, 2 };
                 
    Console.WriteLine(minDistance(a, n));
}
}
 
// This code is contributed by piyush3010

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to find the minimum
    // distance between the minimum
    // and the maximum element
   function minDistance(a, n)
    {
  
        // Stores the minimum and maximum
        // array element
        let max = -1, min = Number.MAX_VALUE;
  
        // Stores the most recently traversed
        // indices of the minimum and the
        // maximum element
        let min_index = -1, max_index = -1;
  
        // Stores the minimum distance
        // between the minimum and the
        // maximum
        let min_dist = n + 1;
  
        // Find the maximum and
        // the minimum element
        // from the given array
        for (let i = 0; i < n; i++) {
            if (a[i] > max)
                max = a[i];
            if (a[i] < min)
                min = a[i];
        }
  
        // Find the minimum distance
        for (let i = 0; i < n; i++) {
  
            // Check if current element
            // is equal to minimum
            if (a[i] == min)
                min_index = i;
  
            // Check if current element
            // is equal to maximum
            if (a[i] == max)
                max_index = i;
  
            // If both the minimum and the
            // maximum element has
            // occurred at least once
            if (min_index != -1
                && max_index != -1)
                min_dist
                    = Math.min(min_dist,
                               Math.abs(min_index
                                        - max_index));
        }
        return min_dist;
    }
    
    // Driver Code
           
        let n = 12;
        let a = [ 3, 2, 1, 2, 1, 4,
                    5, 8, 6, 7, 8, 2 ];
        document.write(minDistance(a, n));
 
</script>

3

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