Dada una array arr[] que consiste en una permutación de los primeros N números naturales, la tarea es encontrar un triplete (i, j, k) de la array dada tal que arr[i] < arr[j] > arr[k] , donde (i < j < k) . Si existen varios tripletes, imprima cualquier triplete válido de índices. De lo contrario, imprima -1 .
Ejemplos:
Entrada: arr[] = {2, 1, 4, 3}
Salida: 1 2 3
Explicación: El triplete que satisface la condición dada es (arr[1], arr[2], arr[3])
Por lo tanto, la salida requerida es 1 2 3 .Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y generar todos los tripletes posibles de la array dada y, para cada triplete, verificar si satisface las condiciones dadas o no. Si se encuentra que es cierto, imprima ese triplete. De lo contrario, imprima -1 .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en las siguientes observaciones:
- Si la array dada se ordena en orden ascendente o descendente desde el rango de índice [1, N – 2] , entonces la solución no existe.
- De lo contrario, existe al menos un índice en la array dada, de modo que el elemento justo antes y después del índice en cuestión es menor que el elemento actual.
Siga los pasos a continuación para resolver el problema:
- Recorra la array dada y para cada índice de array, verifique si el elemento justo antes y después del índice actual es menor que el elemento actual o no. Si se encuentra que es cierto, imprima que el triplete (i – 1, i, i + 1) .
- De lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <iostream>
using namespace std;
// Function to find a triplet
// that satisfy the conditions
void FindTrip(int arr[], int N)
{
// Traverse the given array
for(int i = 1; i < N - 1; i++)
{
// Stores current element
int p = arr[i - 1];
// Stores element just before
// the current element
int q = arr[i];
// Stores element just after
// the current element
int r = arr[i + 1];
// Check the given conditions
if (p < q && q > r)
{
// Print a triplet
cout << i - 1 << " "
<< i << " " << i + 1;
return;
}
}
// If no triplet found
cout << -1;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
FindTrip(arr, N);
return 0;
}
// This code is contributed by jyoti369
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG {
// Function to find a triplet
// that satisfy the conditions
static void FindTrip(int arr[],
int N)
{
// Traverse the given array
for (int i = 1; i < N - 1;
i++) {
// Stores current element
int p = arr[i - 1];
// Stores element just before
// the current element
int q = arr[i];
// Stores element just after
// the current element
int r = arr[i + 1];
// Check the given conditions
if (p < q && q > r) {
// Print a triplet
System.out.println(
(i - 1) + " "
+ (i) + " "
+ (i + 1));
return;
}
}
// If no triplet found
System.out.println(-1);
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 2, 1, 4, 3 };
int N = arr.length;
FindTrip(arr, N);
}
}
Python3
# Python3 program to implement # the above approach # Function to find a triplet # that satisfy the conditions def FindTrip(arr, N): # Traverse the given array for i in range(1, N - 1): # Stores current element p = arr[i - 1] # Stores element just before # the current element q = arr[i] # Stores element just after # the current element r = arr[i + 1] # Check the given conditions if (p < q and q > r): # Print a triplet print(i - 1, i, i + 1) return # If no triplet found print(-1) # Driver Code if __name__ == '__main__': arr = [ 2, 1, 4, 3 ] N = len(arr) FindTrip(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find a triplet
// that satisfy the conditions
static void FindTrip(int[] arr, int N)
{
// Traverse the given array
for(int i = 1; i < N - 1; i++)
{
// Stores current element
int p = arr[i - 1];
// Stores element just before
// the current element
int q = arr[i];
// Stores element just after
// the current element
int r = arr[i + 1];
// Check the given conditions
if (p < q && q > r)
{
// Print a triplet
Console.WriteLine((i - 1) + " " +
(i) + " " + (i + 1));
return;
}
}
// If no triplet found
Console.WriteLine(-1);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 1, 4, 3 };
int N = arr.Length;
FindTrip(arr, N);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find a triplet
// that satisfy the conditions
function FindTrip(arr, N)
{
// Traverse the given array
for (let i = 1; i < N - 1;
i++) {
// Stores current element
let p = arr[i - 1];
// Stores element just before
// the current element
let q = arr[i];
// Stores element just after
// the current element
let r = arr[i + 1];
// Check the given conditions
if (p < q && q > r) {
// Print a triplet
document.write(
(i - 1) + " "
+ (i) + " "
+ (i + 1));
return;
}
}
// If no triplet found
document.write(-1);
}
// Driver Code
let arr = [2, 1, 4, 3 ];
let N = arr.length;
FindTrip(arr, N);
</script>
Producción:
1 2 3
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)