Find the sorted triplet in an array

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[0]);
 findTriplet(arr, n);
 cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2];
}

Output

1 3 5

C

#include<stdio.h>
int ans[3];
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[0] = arr[low];
 ans[1] = arr[mid];
 ans[2] = arr[i];
 return;
 }
 }
 return;
}
intmain()
{
 int arr[] = {1, 4, 3, 5 };
 int n = sizeof(arr)/sizeof(arr[0]);
 findTriplet(arr, n);
 printf("%d %d %d", ans[0], ans[1], ans[2]);
}

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]

People are also reading:

• Python Take list as an input from a user
• Print all subarrays with 0 sum
• Find whether an array is subset of another array
• Merge Two Sorted Arrays in-place
• Program to Rotate an Array
• Sort binary array in linear time
• Print a Man using Graphics
• Find LCM and HCF of two numbers
• Find Maximum Subarray Sum
• Create a mirror of an m–ary Tree