Distancia mínima entre cualquier par especial en la array dada

Dada una array arr[] de N enteros, la tarea es encontrar la mínima diferencia absoluta posible entre los índices de un par especial.

Un par especial se define como un par de índices (i, j) tales que si arr[i] ≤ arr[j] , entonces no hay ningún elemento X (donde arr[i] < X < arr[j]) presente en entre los índices i y j. 
Por ejemplo: 
arr[] = {1, -5, 5} 
Aquí, {1, 5} forma un par especial ya que no hay elementos en el rango (1 a 5) entre arr[0] y arr[2] .

Imprime la mínima diferencia absoluta abs(j – i) tal que el par (i, j) forme un par especial.

Ejemplos:

Entrada: arr[] = {0, -10, 5, -5, 1} 
Salida: 2 
Explicación: 
Los elementos 1 y 5 forman un par especial ya que no hay elementos X en el rango 1 < X < 5 entre ellos , y están a 2 índices uno del otro.

Entrada: arr[] = {3, 3} 
Salida: 1

Enfoque ingenuo: el enfoque más simple es considerar cada par de elementos de la array y verificar si forman un par especial o no. Si es cierto, imprima la distancia mínima entre todos los pares formados.

Complejidad de Tiempo: O(N ³ ) 
Espacio Auxiliar: O(1) 

Enfoque eficiente: para optimizar el enfoque anterior, la idea es observar que solo debemos considerar la distancia entre la posición de los elementos adyacentes en la array ordenada, ya que ese par de elementos no tendrá ningún valor X entre ellos. A continuación se muestran los pasos:

1. Almacene los índices iniciales de los elementos de la array en un mapa .
2. Ordena la array dada arr[] .
3. Ahora, encuentre la distancia entre los índices de los elementos adyacentes de la array ordenada usando Map .
4. Mantenga la distancia mínima para cada par de elementos adyacentes en el paso anterior.
5. Después de completar los pasos anteriores, imprima la distancia mínima formada.

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 that finds the minimum 
// difference between two vectors 
int mindist(vector<int>& left, 
            vector<int>& right) 
{ 
    int res = INT_MAX; 
    for (int i = 0; i < left.size(); ++i) { 
  
        int num = left[i]; 
  
        // Find lower bound of the index 
        int index 
            = lower_bound(right.begin(), 
                        right.end(), num) 
            - right.begin(); 
  
        // Find two adjacent indices 
        // to take difference 
        if (index == 0) 
            res = min(res, 
                    abs(num 
                        - right[index])); 
  
        else if (index == right.size()) 
            res = min(res, 
                    abs(num 
                        - right[index - 1])); 
        else
            res = min(res, 
                    min(abs(num 
                            - right[index - 1]), 
                        abs(num 
                            - right[index]))); 
    } 
  
    // Return the result 
    return res; 
} 
  
// Function to find the minimum distance 
// between index of special pairs 
int specialPairs(vector<int>& nums) 
{ 
    // Stores the index of each element 
    // in the array arr[] 
    map<int, set<int> > m; 
    vector<int> vals; 
  
    // Store the indexes 
    for (int i = 0; 
        i < nums.size(); ++i) { 
        m[nums[i]].insert(i); 
    } 
  
    // Get the unique values in list 
    for (auto p : m) { 
        vals.push_back(p.first); 
    } 
  
    int res = INT_MAX; 
  
    for (int i = 0; 
        i < vals.size(); ++i) { 
  
        vector<int> vec(m[vals[i]].begin(), 
                        m[vals[i]].end()); 
  
        // Take adjacent difference 
        // of same values 
        for (int i = 1; 
            i < vec.size(); ++i) 
            res = min(res, 
                    abs(vec[i] 
                        - vec[i - 1])); 
  
        if (i) { 
            int a = vals[i]; 
  
            // Left index array 
            vector<int> left(m[a].begin(), 
                            m[a].end()); 
  
            int b = vals[i - 1]; 
  
            // Right index array 
            vector<int> right(m[b].begin(), 
                            m[b].end()); 
  
            // Find the minimum gap between 
            // the two adjacent different 
            // values 
            res = min(res, 
                    mindist(left, right)); 
        } 
    } 
    return res; 
} 
  
// Driver Code 
int main() 
{ 
    // Given array 
    vector<int> arr{ 0, -10, 5, -5, 1 }; 
  
    // Function Call 
    cout << specialPairs(arr); 
  
    return 0; 
} 

# Python3 program for the above approach
import sys
  
# Function that finds the minimum
# difference between two vectors
def mindist(left, right):
      
    res = sys.maxsize
      
    for i in range(len(left)):
        num = left[i]
          
        # Find lower bound of the index
        index = right.index(min(
                [i for i in right if num >= i]))
          
        # Find two adjacent indices
        # to take difference
        if (index == 0):
            res = min(res,
                  abs(num - right[index]))
        elif (index == len(right)):
            res = min(res, 
                  min(abs(num - right[index -1]),
                      abs(num - right[index])))
  
    # Return the result
    return res
      
# Function to find the minimum distance
# between index of special pairs
def specialPairs(nums):
      
    # Stores the index of each element
    # in the array arr[]
    m = {}
    vals = []
  
    for i in range(len(nums)):
        m[nums[i]] = i
          
    for p in m:
        vals.append(p)
      
    res = sys.maxsize
      
    for i in range(1, len(vals)):
        vec = [m[vals[i]]]
          
        # Take adjacent difference
        # of same values
        for i in range(1, len(vec)):
            res = min(res,
                      abs(vec[i] - vec[i - 1]))
              
        if (i):
            a = vals[i]
              
            # Left index array
            left = [m[a]]
              
            b = vals[i - 1]
              
            # Right index array
            right = [m[b]]
              
            # Find the minimum gap between
            # the two adjacent different
            # values
            res = min(res,
                      mindist(left, right)) + 1
      
    return res
  
# Driver Code
if __name__ == "__main__":
      
    # Given array 
    arr = [ 0, -10, 5, -5, 1 ]
  
    # Function call
    print(specialPairs(arr))
  
# This code is contributed by dadi madhav

2

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