# Find the sorted triplet in an array

Posted in  Last updated on December 7, 2023

## Problem

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

#### Sample Input

`[ 2, 5, 4, 6 ]`

#### Sample Output

`2 5 6`

### Brute Force Approach

We can traverse the array and consider each element of the array as the middle element and see if we can find one element smaller than it on its left side and one element greater than it on the right side. This approach will take O(N2) time.

### Efficient Approach

We can traverse through the array and keep track of the minimum element so far. low will store the minimum value index in the triplet, mid will store the index of the middle element of the triplet. If we encounter a variable that is more than the minimum element so far, update low and mid.

If we find better candidates for the same, we update these two variables. While traversing the array, if we find some element as greater than the element at mid, we find our triplet.

#### C++

```#include <iostream>
#include <vector>
#include <tuple>
usingnamespacestd;
vector<int>ans;
voidfindTriplet(int arr[], int n)
{
int minIndex = 0;
int low, mid = -1;
for (int i = 1; i < n; i++)
{
if (arr[i] <= arr[minIndex]) {
minIndex = i;
}
elseif (mid == -1) {
low = minIndex;
mid = i;
}
elseif (arr[i] <= arr[mid]) {
low = minIndex;
mid = i;
}
else {
ans.push_back(arr[low]);
ans.push_back(arr[mid]);
ans.push_back(arr[i]);
return;
}
}
return;
}
intmain()
{
int arr[] = {1, 4, 3, 5 };
int n = sizeof(arr)/sizeof(arr);
findTriplet(arr, n);
cout<<ans<<" "<<ans<<" "<<ans;
}
```

#### Output

`1 3 5`

#### C

```#include<stdio.h>
int ans;
voidfindTriplet(int arr[], int n)
{
int minIndex = 0;
int low, mid = -1;
for (int i = 1; i < n; i++)
{
if (arr[i] <= arr[minIndex]) {
minIndex = i;
}
elseif (mid == -1) {
low = minIndex;
mid = i;
}
elseif (arr[i] <= arr[mid]) {
low = minIndex;
mid = i;
}
else {
ans = arr[low];
ans = arr[mid];
ans = arr[i];
return;
}
}
return;
}
intmain()
{
int arr[] = {1, 4, 3, 5 };
int n = sizeof(arr)/sizeof(arr);
findTriplet(arr, n);
printf("%d %d %d", ans, ans, ans);
}```

#### Output

`1 3 5`

#### Python

```ans = []
def findTriplet(arr):
n = len(arr)
if n < 3:
return None
minIndex = 0
low = 0
mid = -1
for i in range(1, n):
if arr[i] <= arr[minIndex]:
minIndex = i
elif mid == -1:
low = minIndex
mid = i
elif arr[i] <= arr[mid]:
low = minIndex
mid = i
else:
ans.append(arr[low])
ans.append(arr[mid])
ans.append(arr[i])
return
input = [1, 4, 3, 5]
findTriplet(input)
print(ans)```

Output

`[1, 3, 5]`