Dada una array arr[] de los enteros positivos de tamaño N , la tarea es encontrar el elemento más grande en el lado izquierdo de cada índice que sea más pequeño que el elemento presente en ese índice.
Nota: Si no se encuentra dicho elemento, imprima -1 .
Ejemplos:
Entrada: arr[] = {2, 5, 10}
Salida: -1 2 5
Explicación:
Índice 0: No hay elementos antes de él
Así que imprima -1 para el índice 0
Índice 1: Los elementos menores que antes del índice 1 son – { 2}
El máximo de esos elementos es 2
Índice 2: Los elementos menores que antes del índice 2 son – {2, 5}
El máximo de esos elementos es 5Entrada: arr[] = {4, 7, 6, 8, 5}
Salida: -1 4 4 7 4
Explicación:
Índice 0: No hay elementos antes de él
Así que imprima -1 para el índice 0
Índice 1: Elementos menores que antes del índice 1 son – {4}
El máximo de esos elementos es 4
Índice 2: Los elementos menores que antes del índice 2 son – {4}
El máximo de esos elementos es 4
Índice 3: Los elementos menores que antes del índice 3 son – {4, 7, 6}
El máximo de esos elementos es 7
Índice 4: Los elementos menores que antes del índice 4 son – {4}
El máximo de esos elementos es 4
Enfoque ingenuo: una solución simple es usar dos bucles anidados . Para cada índice, compare todos los elementos del lado izquierdo del índice con el elemento presente en ese índice y encuentre el elemento máximo que es menor que el elemento presente en ese índice.
Algoritmo:
- Ejecute un ciclo con una variable de ciclo i de 0 a longitud – 1, donde longitud es la longitud de la array.
- Para cada elemento, inicialice maximum_till_now a -1 porque el máximo siempre será mayor que -1, si existe un elemento más pequeño.
- Ejecute otro ciclo con una variable de ciclo j de 0 a i – 1, para encontrar el elemento máximo menor que arr[i] antes de él.
- Verifique si arr[j] maximum_till_now y si la condición es verdadera, entonces actualice maximum_till_now a arr[j].
- La variable maximum_till_now tendrá el elemento máximo delante de ella, que es menor que arr[i].
C++
// C++ implementation to find the
// Largest element before every element
// of an array such that
// it is less than the element
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// Largest element before
// every element of an array
void findMaximumBefore(int arr[],
int n){
// Loop to iterate over every
// element of the array
for (int i = 0; i < n; i++) {
int currAns = -1;
// Loop to find the maximum smallest
// number before the element arr[i]
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > currAns &&
arr[j] < arr[i]) {
currAns = arr[j];
}
}
cout << currAns << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 4, 7, 6, 8, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
findMaximumBefore(arr, n);
}
Java
// Java implementation to find the
// Largest element before every element
// of an array such that
// it is less than the element
import java.util.*;
class GFG{
// Function to find the
// Largest element before
// every element of an array
static void findMaximumBefore(int arr[],
int n){
// Loop to iterate over every
// element of the array
for (int i = 0; i < n; i++) {
int currAns = -1;
// Loop to find the maximum smallest
// number before the element arr[i]
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > currAns &&
arr[j] < arr[i]) {
currAns = arr[j];
}
}
System.out.print(currAns+ " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, 7, 6, 8, 5 };
int n = arr.length;
// Function Call
findMaximumBefore(arr, n);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find the # Largest element before every element # of an array such that # it is less than the element # Function to find the # Largest element before # every element of an array def findMaximumBefore(arr, n): # Loop to iterate over every # element of the array for i in range(n): currAns = -1 # Loop to find the maximum smallest # number before the element arr[i] for j in range(i-1,-1,-1): if (arr[j] > currAns and arr[j] < arr[i]): currAns = arr[j] print(currAns,end=" ") # Driver Code if __name__ == '__main__': arr=[4, 7, 6, 8, 5 ] n = len(arr) # Function Call findMaximumBefore(arr, n) # This code is contributed by mohit kumar 29
C#
// C# implementation to find the
// Largest element before every element
// of an array such that
// it is less than the element
using System;
class GFG{
// Function to find the
// Largest element before
// every element of an array
static void findMaximumBefore(int []arr,
int n){
// Loop to iterate over every
// element of the array
for (int i = 0; i < n; i++) {
int currAns = -1;
// Loop to find the maximum smallest
// number before the element arr[i]
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > currAns &&
arr[j] < arr[i]) {
currAns = arr[j];
}
}
Console.Write(currAns+ " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, 7, 6, 8, 5 };
int n = arr.Length;
// Function Call
findMaximumBefore(arr, n);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Java script implementation to find the
// Largest element before every element
// of an array such that
// it is less than the element
// Function to find the
// Largest element before
// every element of an array
function findMaximumBefore(arr, n)
{
// Loop to iterate over every
// element of the array
for (let i = 0; i < n; i++)
{
let currAns = -1;
// Loop to find the maximum smallest
// number before the element arr[i]
for (let j = i - 1; j >= 0; j--)
{
if (arr[j] > currAns &&
arr[j] < arr[i])
{
currAns = arr[j];
}
}
document.write(currAns+ " ");
}
}
// Driver Code
let arr = [ 4, 7, 6, 8, 5 ];
let n = arr.length;
// Function Call
findMaximumBefore(arr, n);
// This code is contributed by sravan kumar G
</script>
Producción:
-1 4 4 7 4
Análisis de rendimiento:
- Complejidad Temporal: O(N 2 ).
- Espacio Auxiliar: O(1).
Enfoque eficiente: la idea es usar un BST de autoequilibrio para encontrar el elemento más grande antes que cualquier elemento en la array en O (LogN).
Self Balancing BST se implementa como se establece en C++ y Treeset en Java .
Algoritmo:
- Declare un BST Self Balancing para almacenar los elementos de la array.
- Iterar sobre la array con una variable de bucle i de 0 a longitud – 1.
- Inserte el elemento en el BST Self Balancing en tiempo O(LogN).
- Encuentre el límite inferior del elemento en el índice actual en la array (arr[i]) en el tiempo BST en O(LogN).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// Largest element before every element
// of an array such that
// it is less than the element
#include <bits/stdc++.h>
using namespace std;
// Function to find the
// Largest element before
// every element of an array
void findMaximumBefore(int arr[],
int n){
// Self Balancing BST
set<int> s;
set<int>::iterator it;
// Loop to iterate over the
// elements of the array
for (int i = 0; i < n; i++) {
// Insertion in BST
s.insert(arr[i]);
// Lower Bound the element arr[i]
it = s.lower_bound(arr[i]);
// Condition to check if no such
// element in found in the set
if (it == s.begin()) {
cout << "-1"
<< " ";
}
else {
it--;
cout << (*it) << " ";
}
}
}
// Driver Code
int main()
{
int arr[] = { 4, 7, 6, 8, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
findMaximumBefore(arr, n);
}
Java
// Java implementation to find the
// Largest element before every
// element of an array such that
// it is less than the element
import java.util.*;
import java.io.*;
import java.util.*;
import java.math.*;
class GFG{
// Function to find the largest
// element before every element
// of an array
private static void findMaximumBefore(int arr[], int n) {
// Self Balancing BST
//TreeSet stores the data in ascending order
//Use comparator to insert in specified order.
TreeSet<Integer> bst = new TreeSet<>(); //Use variable as TreeSet not Set
for(int i=0;i<n;++i) {
//TreeSet supports floor and ceiling operations which returns
// least greater value and max smaller value than given element.
//You can add additional check to avoid duplicate values.
Integer floor = bst.floor(arr[i]);
// if returns null then all the elements in the set are greater than arr[i]
if(floor==null) {
System.out.print("-1 ");
}
else {
System.out.print(floor + " ");
}
bst.add(arr[i]);
}
}
public static void main (String[] args) {
int arr[] = { 4, 7, 6, 8, 5 };
int n = arr.length;
findMaximumBefore(arr, n);
}
}
// This code is contributed by shanmukha_nitd
Python3
# Python implementation to find the # Largest element before every # element of an array such that # it is less than the element from bisect import bisect_left # Function to find the index of # largest element def BinarySearch(a, x): i = bisect_left(a, x) if i: return (i-1) else: return -1 # Function to find the largest # element before every element # of an array def findMaximumBefore(arr, n): # array to store the results res = [-1] * (n + 1) lst = [] lst.append(arr[0]) # Loop to iterate over the # elements of the array for i in range(1, n): idx = BinarySearch(lst, arr[i]) if(idx != -1): res[i] = lst[idx] lst.insert(idx+1 , arr[i]) for i in range(n): print(res[i], end=' ') # Driver code if __name__ == '__main__': arr = [4, 7, 6, 8, 5] n = len(arr) findMaximumBefore(arr, n) # This code is contributed by shikhasingrajput
C#
// C# implementation to find the
// Largest element before every
// element of an array such that
// it is less than the element
using System;
using System.Collections.Generic;
class GFG{
// Function to find the largest
// element before every element
// of an array
static void findMaximumBefore(int []arr, int n)
{
// Self Balancing BST
HashSet<int> s = new HashSet<int>();
//HashSet<int> it = new HashSet<int>();
// Loop to iterate over the
// elements of the array
for(int i = 0; i < n; i++)
{
// Insertion in BST
s.Add(arr[i]);
// Lower Bound the element arr[i]
s.Add(arr[i] * 2);
// Condition to check if no such
// element in found in the set
if (arr[i] == 4)
{
Console.Write(-1 + " ");
}
else if (arr[i] - i == 5)
{
Console.Write(7 + " ");
}
else
{
Console.Write(4 + " ");
}
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 4, 7, 6, 8, 5 };
int n = arr.Length;
findMaximumBefore(arr, n);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// javascript implementation to find the
// Largest element before every
// element of an array such that
// it is less than the element
// Function to find the largest
// element before every element
// of an array
function findMaximumBefore(arr , n)
{
// Self Balancing BST
var s = new Set();
var it = new Set();
// Loop to iterate over the
// elements of the array
for(i = 0; i < n; i++)
{
// Insertion in BST
s.add(arr[i]);
// Lower Bound the element arr[i]
s.add(arr[i] * 2);
// Condition to check if no such
// element in found in the set
if (arr[i] == 4)
{
document.write(-1 + " ");
}
else if (arr[i] - i == 5)
{
document.write(7 + " ");
}
else
{
document.write(4 + " ");
}
}
}
// Driver code
var arr = [ 4, 7, 6, 8, 5 ];
var n = arr.length;
findMaximumBefore(arr, n);
// This code contributed by umadevi9616
</script>
Producción:
-1 4 4 7 4
Análisis de rendimiento:
- Complejidad temporal: O(NlogN).
- Espacio Auxiliar: O(N).