Given an array arr[], the task is to find the lexicographically largest triplet in that array that can form a triangle. If no such triplet exists, print -1.
Example:
Input: arr[] = { 4, 2, 10, 3, 5 }
Output: 3 4 5
Explanation:
The lexicographically largest triplet is (4, 5, 10). But it does not form a triangle.
The next lexicographically largest triplet is (3, 4, 5).
Since it forms a triangle, it is the required answer.
Input: arr[] = { 20, 12, 120, 3, 15 }
Output: 12 15 20
Approach:
A triplet can form a triangle if and only if it follows the condition given below:
If A, B and C forms a triplet, then the triplet can form a triangle if
A < B + C or B < A + C or C < A + B
The idea is to use Sorting. Sort the array in ascending order. Start traversing from the end of the array and check if any triplet satisfies the above condition. Print the first triplet to satisfy the condition, as the output. If no such triplet can be found, then print -1.
Below is the implementation of the above approach:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find lexicographically // largest triplet that forms a // triangle in the given array void findTriplet( int arr[], int N) { // Sort the array sort(arr, arr + N); int flag = 0, i; // Iterate from the end of the array for (i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break ; } } // If triplet found if (flag) { // Print the triplet cout << arr[i - 2] << " " << arr[i - 1] << " " << arr[i] << endl; } // Otherwise else { cout << -1 << endl; } } // Driver Code int main() { int arr[] = { 4, 2, 10, 3, 5 }; int N = sizeof (arr) / sizeof (arr[0]); findTriplet(arr, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find lexicographically // largest triplet that forms a // triangle in the given array static void findTriplet( int arr[], int N) { // Sort the array Arrays.sort(arr); int flag = 0 , i; // Iterate from the end of the array for (i = N - 1 ; i - 2 >= 0 ; i--) { // If the triplet forms a triangle if (arr[i - 2 ] + arr[i - 1 ] > arr[i]) { flag = 1 ; break ; } } // If triplet found if (flag != 0 ) { // Print the triplet System.out.println(arr[i - 2 ] + " " + arr[i - 1 ] + " " + arr[i] ); } // Otherwise else { System.out.println(- 1 ); } } // Driver Code public static void main (String []args) { int arr[] = { 4 , 2 , 10 , 3 , 5 }; int N = arr.length; findTriplet(arr, N); } } // This code is contributed by chitranayal |
Python3
# Python3 implementation of # the above approach # Function to find lexicographically # largest triplet that forms a # triangle in the given array def findTriplet(arr, N): # Sort the array arr.sort() # Iterate from the end of the array i = N - 1 while i - 2 > = 0 : # If the triplet forms a triangle if (arr[i - 2 ] + arr[i - 1 ] > arr[i]): flag = 1 break i - = 1 # If triplet found if (flag): # Print the triplet print (arr[i - 2 ], arr[i - 1 ], arr[i]) # Otherwise else : print ( - 1 ) # Driver Code if __name__ = = '__main__' : arr = [ 4 , 2 , 10 , 3 , 5 ] N = len (arr) findTriplet(arr, N) # This code is contributed by Shivam Singh |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to find lexicographically // largest triplet that forms a // triangle in the given array static void findTriplet( int []arr, int N) { // Sort the array Array.Sort(arr); int flag = 0, i; // Iterate from the end of the array for (i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break ; } } // If triplet found if (flag != 0) { // Print the triplet Console.Write(arr[i - 2] + " " + arr[i - 1] + " " + arr[i] ); } // Otherwise else { Console.Write(-1); } } // Driver Code public static void Main ( string []args) { int []arr = { 4, 2, 10, 3, 5 }; int N = arr.Length; findTriplet(arr, N); } } // This code is contributed by Ritik Bansal |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find lexicographically // largest triplet that forms a // triangle in the given array function findTriplet(arr, N) { // Sort the array arr.sort((a, b) => a - b); var flag = 0, i; // Iterate from the end of the array for (i = N - 1; i - 2 >= 0; i--) { // If the triplet forms a triangle if (arr[i - 2] + arr[i - 1] > arr[i]) { flag = 1; break ; } } // If triplet found if (flag) { // Print the triplet document.write( arr[i - 2] + " " + arr[i - 1] + " " + arr[i] + "<br>" ); } // Otherwise else { document.write(-1 + "<br>" ); } } // Driver Code var arr = [4, 2, 10, 3, 5]; var N = arr.length; findTriplet(arr, N); </script> |
3 4 5
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!