Encuentre el valor más cercano presente a la izquierda de cada elemento de la array

Dada una array arr[] de tamaño N , la tarea para cada elemento de la array es encontrar el valor no igual más cercano presente a su izquierda en la array. Si no se encuentra dicho elemento, imprima -1

Ejemplos:

Entrada: arr[] = { 2, 1, 5, 8, 3 }
Salida: -1 2 2 5 2
Explicación:
[ 2 ], es el único número en este prefijo. Por lo tanto, la respuesta es -1. 
[2, 1 ], el número más cercano a 1 es 2
[2, 1, 5 ], el número más cercano a 5 es 2
[2, 1, 5, 8 ], el número más cercano a 8 es 5 
[2, 1, 5, 8, 3 ], el número más cercano a 3 es 2

Entrada: arr[] = {3, 3, 2, 4, 6, 5, 5, 1}
Salida: -1 -1 3 3 4 4 4 2
Explicación:
[3], es el único número en este prefijo. Por lo tanto, la respuesta es -1. 
[3, 3], es el único número en este prefijo. Por lo tanto, la respuesta es -1
[3, 3, 2], el número más cercano a 2 es 3
[3, 3, 2, 4], el número más cercano a 4 es 3 
[3, 3, 2, 4, 6], el número más cercano a 6 es 4
[3, 3, 2, 4, 6, 5], el número más cercano a 5 es 4
[3, 3, 2, 4, 6, 5, 5], el número más cercano a 5 es 4
[3, 3, 2, 4, 6, 5, 5, 1], el número más cercano a 1 es 2

Enfoque ingenuo: la idea más simple es recorrer la array dada y, para cada i- ^ésimo elemento, encontrar el elemento más cercano en el lado izquierdo del índice i que no sea igual a arr[i] . 
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)

Enfoque eficiente: 

La idea es insertar los elementos de la array dada en un Conjunto de manera que los números insertados se ordenen y luego, para un número entero, encuentre su posición y compare su siguiente valor con el valor anterior, e imprima el valor más cercano de los dos.
Siga los pasos a continuación para resolver el problema:

• Inicialice un Conjunto de enteros S para almacenar los elementos en orden ordenado .
• Recorra la array arr[] usando la variable i .
• Ahora, encuentre el valor más cercano más pequeño y más grande que arr[i] , digamos X e Y respectivamente.
  • Si no se puede encontrar X , imprima Y .
  • Si no se puede encontrar Y , imprima Z.
  • Si no se pueden encontrar tanto X como Y , imprima “-1” .
• Después de eso, agregue arr[i] al Conjunto S e imprima X si abs(X – arr[i]) es menor que abs(Y – arr[i]) . De lo contrario, imprima Y .
• Repita los pasos anteriores para cada elemento.

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 find the closest number on
// the left side of x
void printClosest(set<int>& streamNumbers, int x)
{
 
    // Insert the value in set and store
    // its position
    auto it = streamNumbers.insert(x).first;
 
    // If x is the smallest element in set
    if (it == streamNumbers.begin())
    {
        // If count of elements in the set
        // equal to 1
        if (next(it) == streamNumbers.end())
        {
 
            cout << "-1 ";
            return;
        }
 
        // Otherwise, print its
        // immediate greater element
        int rightVal = *next(it);
        cout << rightVal << " ";
        return;
    }
 
    // Store its immediate smaller element
    int leftVal = *prev(it);
 
    // If immediate greater element does not
    // exists print it's immediate
    // smaller element
    if (next(it) == streamNumbers.end()) {
        cout << leftVal << " ";
        return;
    }
 
    // Store the immediate
    // greater element
    int rightVal = *next(it);
 
    // Print the closest number
    if (x - leftVal <= rightVal - x)
        cout << leftVal << " ";
    else
        cout << rightVal << " ";
}
 
// Driver Code
int main()
{
 
    // Given array
    vector<int> arr = { 3, 3, 2, 4, 6, 5, 5, 1 };
 
    // Initialize set
    set<int> streamNumbers;
 
    // Print Answer
    for (int i = 0; i < arr.size(); i++) {
 
        // Function Call
        printClosest(streamNumbers, arr[i]);
    }
 
    return 0;
}

-1 -1 3 3 4 4 4 2 

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