Given an array arr[], the task is to check that if there exist a triplet (i, j, k) such that arr[i]<arr[k]<arr[j] and i<j<k then print Yes else print No.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: No
Explanation:
There is no such sub-sequence such that arr[i] < arr[k] < arr[j]Input: arr[] = {3, 1, 5, 0, 4}
Output: Yes
Explanation:
There exist a triplet (3, 5, 4) which is arr[i] < arr[k] < arr[j]
Naive Approach: The idea is to generate all possible triplets and if any triplets satisfy the given conditions the print Yes else print No.
Below is the implementation of the above approach:
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 Codeint 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 arrayarr = [ 4, 7, 5, 6 ]# Function Callif (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 arraylet arr = [ 4, 7, 5, 6 ];// Function Callif (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 approachimport 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 codepublic 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 |
Output:
Yes
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is to use the stack to keep the track of the smaller elements in the right of every element in the array arr[]. Below are the steps:
- Traverse the array from the end and maintain a stack which stores the element in the decreasing order.
- To maintain the stack in decreasing order, pop the elements which are smaller than the current element. Then mark the popped element as the third element of the triplet.
- While traversing the array in reverse if any element is less than the last popped element(which is marked as the third element of the triplet). Then their exist a triplet which satisfy the given condition and print Yes.
- Otherwise print No.
Below is the implementation of the above approach:
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 h3 // 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 Codeint 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 h3 // 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 codepublic 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 approachimport 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 Codeif __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 h3 // 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 codepublic 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 h3 // 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 arrayvar arr = [4, 7, 5, 6 ];// Function Callif (findTriplet(arr)) { document.write( " Yes");}else { document.write( " No" );}</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
