Find a sorted triplet in the given array

Given an array A[] of integers, efficiently find a sorted triplet such that A[i] < A[j] < A[k] and 0 <= i < j < k < n where n is the size of the array.


 

For example,


Input: A[] = { 5, 4, 3, 7, 6, 1, 9 }

Output: Any one of below triplets:

(5, 7, 9)
(4, 7, 9)
(3, 7, 9)
(5, 6, 9)
(4, 6, 9)
(3, 6, 9)

 
Simple solution is to traverse the array and for each index, simply check if at-least one smaller and one larger element exists on its left and right respectively. If any such index exists, we have found our triplet. The time complexity of above solution is O(n2) since for each array element, we might end up traversing the whole array again.

 
We can easily solve this problem in linear time using some extra space. The idea is to create two auxillary arrays. Each index of the first array stores the index of smaller element to the left and each index of the second array stores the index of larger element to the right. After filling up both arrays, we find an index which has both smaller element present to its left and larger element to its right. If any such index exists, we have found our triplet.

 

Download   Run Code

Output:

Triplet found: (3, 7, 9)

 
The time complexity of above solution is O(n) since the solution iterates over the whole array thrice. The extra space required by the solution is O(n) for storing the auxiliary arrays.

 
We can even solve this problem in linear time and constant extra space. The idea is to traverse the array from left to right and keep track of minimum element found so far. We also maintain two variables low and mid for storing the indices of first two elements of the triplet. Then for the first element which is more than the current minimum, we initialize the low and mid index with the indices of current minimum and current element respectively. If we see a better candidate for the middle element, we update the mid index along with the low index. If at any point, we encounter an element which is more than the middle element, then we’re done and we have found the triplet.

 

Download   Run Code

Output:

Triplet found: (3, 6, 9)

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of