Comprobar si existe un triplete (i, j, k) tal que arr[i] < arr[k] < arr[j] para i < j < k

Dada una array arr[] , la tarea es verificar que si existe un triplete (i, j, k) tal que arr[i]<arr[k]<arr[j] e i<j<k entonces imprima de lo contrario imprima No.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: No
Explicación:
No existe tal subsecuencia tal que arr[i] < arr[k] < arr[j]

Entrada: arr[] = {3, 1, 5, 0, 4}
Salida:
Explicación:
Existe un triplete (3, 5, 4) que es arr[i] < arr[k] < arr[j]

Enfoque ingenuo: la idea es generar todos los tripletes posibles y, si alguno de los tripletes satisface las condiciones dadas, imprime , de lo contrario, imprime  No.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
 
using namespace std;
 
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
bool findTriplet(vector<int> nums)
{
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            for (int k = j + 1; k < nums.size(); k++) {
                // Triplet found, hence return false
                if (nums[i] < nums[k] && nums[k] < nums[j])
                    return true;
            }
        }
    }
    // No triplet found, hence return false
    return false;
}
 
// Driver Code
int main()
{
    // Given array
    vector<int> arr = { 4, 7, 5, 6 };
 
    // Function Call
    if (findTriplet(arr)) {
        cout << " Yes" << '\n';
    }
    else {
        cout << " No" << '\n';
    }
    return 0;
}

Python3

# Python3 program for the above approach
 
# Function to check if there exist
# triplet in the array such that
# i < j < k and arr[i] < arr[k] < arr[j]
def findTriplet(nums):
 
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            for k in range(j + 1, len(nums)):
               
                # Triplet found, hence return false
                if(nums[i] < nums[k] and nums[k] < nums[j]):
                    return True
                     
    # No triplet found, hence return false
    return False
 
# Driver Code
 
# Given array
arr = [ 4, 7, 5, 6 ]
 
# Function Call
if (findTriplet(arr)):
    print(" Yes")
 
else:
    print(" No")
 
 # This code is contributed by shinjanpatra

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
function findTriplet(nums)
{
    for (let i = 0; i < nums.length; i++)
    {
        for (let j = i + 1; j < nums.length; j++)
        {
            for (let k = j + 1; k < nums.length; k++)
            {
             
                // Triplet found, hence return false
                if (nums[i] < nums[k] && nums[k] < nums[j])
                    return true;
            }
        }
    }
     
    // No triplet found, hence return false
    return false;
}
 
// Driver Code
 
// Given array
let arr = [ 4, 7, 5, 6 ];
 
// Function Call
if (findTriplet(arr)) {
    document.write(" Yes","</br>")
}
else {
    document.write(" No","</br>")
}
 
// This code is contributed by shinjanpatra
 
</script>

C#

// C# program for the above approach
     
using System;
 
public class HelloWorld
{
    // Function to check if there exist
    // triplet in the array such that
    // i < j < k and arr[i] < arr[k] < arr[j]
    public static bool findTriplet(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++) {
            for (int j = i + 1; j < nums.Length; j++) {
                for (int k = j + 1; k < nums.Length; k++) {
                    // Triplet found, hence return false
                    if (nums[i] < nums[k] && nums[k] < nums[j])
                        return true;
                }
            }
        }
        // No triplet found, hence return false
        return false;
    }
     
     
    public static void Main(string[] args)
    {
        // Given array
        int []arr = { 4, 7, 5, 6 };
      
        // Function Call
        if (findTriplet(arr)) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }
}
 
// This code is contributed by CodeWithMini

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
public static boolean findTriplet(int[] nums)
{
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            for (int k = j + 1; k < nums.length; k++) {
                // Triplet found, hence return false
                if (nums[i] < nums[k] && nums[k] < nums[j])
                    return true;
            }
        }
    }
    // No triplet found, hence return false
    return false;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 4, 7, 5, 6 };
 
    // Function call
    if (findTriplet(arr))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by CodeWithMini

Producción: 

Yes

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

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la pila para realizar un seguimiento de los elementos más pequeños a la derecha de cada elemento de la array arr[] . A continuación se muestran los pasos:
 

  • Atraviese la array desde el final y mantenga una pila que almacene el elemento en orden decreciente.
  • Para mantener la pila en orden decreciente, extraiga los elementos que son más pequeños que el elemento actual. Luego marque el elemento reventado como el tercer elemento del triplete.
  • Mientras recorre la array en sentido inverso, si algún elemento es menor que el último elemento extraído (que está marcado como el tercer elemento del triplete). Entonces existe un triplete que satisface la condición dada e imprime .
  • De lo contrario , imprima No.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
bool findTriplet(vector<int>& arr)
{
    int n = arr.size();
    stack<int> st;
 
    // Initialize the heights of h1 and h2
    // to INT_MAX and INT_MIN respectively
    int h3 = INT_MIN, h1 = INT_MAX;
    for (int i = n - 1; i >= 0; i--) {
 
        // Store the current element as h1
        h1 = arr[i];
 
        // If the element at top of stack
        // is less than the current element
        // then pop the stack top
        // and keep updating the value of h3
        while (!st.empty()
            && st.top() < arr[i]) {
 
            h3 = st.top();
            st.pop();
        }
 
        // Push the current element
        // on the stack
        st.push(arr[i]);
 
        // If current element is less
        // than h3, then we found such
        // triplet and return true
        if (h1 < h3) {
            return true;
        }
    }
 
    // No triplet found, hence return false
    return false;
}
 
// Driver Code
int main()
{
    // Given array
    vector<int> arr = { 4, 7, 5, 6 };
 
    // Function Call
    if (findTriplet(arr)) {
        cout << " Yes" << '\n';
    }
    else {
        cout << " No" << '\n';
    }
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
public static boolean findTriplet(int[] arr)
{
    int n = arr.length;
    Stack<Integer> st = new Stack<>();
 
    // Initialize the heights of h1 and h2
    // to INT_MAX and INT_MIN respectively
    int h3 = Integer.MIN_VALUE;
    int h1 = Integer.MAX_VALUE;
 
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Store the current element as h1
        h1 = arr[i];
 
        // If the element at top of stack
        // is less than the current element
        // then pop the stack top
        // and keep updating the value of h3
        while (!st.empty() && st.peek() < arr[i])
        {
            h3 = st.peek();
            st.pop();
        }
 
        // Push the current element
        // on the stack
        st.push(arr[i]);
 
        // If current element is less
        // than h3, then we found such
        // triplet and return true
        if (h1 < h3)
        {
            return true;
        }
    }
 
    // No triplet found, hence return false
    return false;
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 4, 7, 5, 6 };
 
    // Function call
    if (findTriplet(arr))
    {
        System.out.println("Yes");
    }
    else
    {
        System.out.println("No");
    }
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for the above approach
import sys
 
# Function to check if there exist
# triplet in the array such that
# i < j < k and arr[i] < arr[k] < arr[j]
def findTriplet(arr):
    n = len(arr)
    st = []
 
    # Initialize the heights of h1 and h3
    # to INT_MAX and INT_MIN respectively
    h3 = -sys.maxsize - 1
    h1 = sys.maxsize
     
    for i in range(n - 1, -1, -1):
 
        # Store the current element as h1
        h1 = arr[i]
 
        # If the element at top of stack
        # is less than the current element
        # then pop the stack top
        # and keep updating the value of h3
        while (len(st) > 0 and st[-1] < arr[i]):
            h3 = st[-1]
            del st[-1]
 
        # Push the current element
        # on the stack
        st.append(arr[i])
 
        # If current element is less
        # than h3, then we found such
        # triplet and return true
        if (h1 < h3):
            return True
         
    # No triplet found, hence
    # return false
    return False
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [ 4, 7, 5, 6 ]
 
    # Function Call
    if (findTriplet(arr)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
public static bool findTriplet(int[] arr)
{
    int n = arr.Length;
    Stack<int> st = new Stack<int>();
 
    // Initialize the heights of h1 and h2
    // to INT_MAX and INT_MIN respectively
    int h3 = int.MinValue;
    int h1 = int.MaxValue;
 
    for(int i = n - 1; i >= 0; i--)
    {
         
        // Store the current element as h1
        h1 = arr[i];
 
        // If the element at top of stack
        // is less than the current element
        // then pop the stack top
        // and keep updating the value of h3
        while (st.Count != 0 && st.Peek() < arr[i])
        {
            h3 = st.Peek();
            st.Pop();
        }
 
        // Push the current element
        // on the stack
        st.Push(arr[i]);
 
        // If current element is less
        // than h3, then we found such
        // triplet and return true
        if (h1 < h3)
        {
            return true;
        }
    }
 
    // No triplet found, hence return false
    return false;
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 4, 7, 5, 6 };
 
    // Function call
    if (findTriplet(arr))
    {
        Console.WriteLine("Yes");
    }
    else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to check if there exist
// triplet in the array such that
// i < j < k and arr[i] < arr[k] < arr[j]
function findTriplet(arr)
{
    var n = arr.length;
    var st = [];
 
    // Initialize the heights of h1 and h2
    // to INT_MAX and INT_MIN respectively
    var h3 = -1000000000, h1 = 1000000000;
    for (var i = n - 1; i >= 0; i--) {
 
        // Store the current element as h1
        h1 = arr[i];
 
        // If the element at top of stack
        // is less than the current element
        // then pop the stack top
        // and keep updating the value of h3
        while (st.length!=0
            && st[st.length-1] < arr[i]) {
 
            h3 = st[st.length-1];
            st.pop();
        }
 
        // Push the current element
        // on the stack
        st.push(arr[i]);
 
        // If current element is less
        // than h3, then we found such
        // triplet and return true
        if (h1 < h3) {
            return true;
        }
    }
 
    // No triplet found, hence return false
    return false;
}
 
// Driver Code
// Given array
var arr = [4, 7, 5, 6 ];
// Function Call
if (findTriplet(arr)) {
    document.write( " Yes");
}
else {
    document.write( " No" );
}
 
 
</script>
Producción: 

Yes

 

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

Publicación traducida automáticamente

Artículo escrito por mukulkumar10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *