# Find a sorted subsequence of size 3 in linear time

Difficulty Level Medium
ArrayViews 2023

## Problem Statement

The problem “Find a sorted subsequence of size 3 in linear time” states that you have an integer array. The problem statement asks to find out the three numbers in such a way that array[i] < array [k] < array[k], and i < j < k.

## Example

`arr[] = {11,34,2,5,1,7,4 }`
`2 5 7`

Explanation

2 is less than 5 and 5 is less than 7, and such that their indexes are less than each other.

## Algorithm

```1. Declare a new array “small” and “great” of size as same as the original array.
2. Set the value of maximum to n-1, and the value of minimum to 0.
3. Marked the first element of the array we created to -1.
4. Traverse the array from i=1 to less than n(n is the length of the array).
1. Check if arr[i] is smaller or equal to arr[minimum], if true
1. Set minimum to i and small[i] to -1.
2. Else put small[i] = minimum.
5. Traverse the array from i=n-2 to less than equal to 0(n is the length of the array).
1. Check if arr[i] is greater than or equal to arr[maximum], if true
1. Set maximum to i and great[i] to -1.
2. Else put great[i] = maximum.
6. Traverse the array from i=0 to n and check if small[i] and great[i] is not equal to -1, then print the arr[small[i]] , arr[i] and arr[great[i]].
1. Return```

### Explanation

We have an array of integer. We have asked to find out the sorted subsequence in the given array. Sorted subsequence contains three numbers which we have to find in sorted order and it should be in sequence, not contiguously but in sequence, the first number should be less than the second number and second number should be less than the third number, and first, second and third should come in order.

We are going to traverse the array from 1 to less than n, we will leave the first and last index element as it is. Because we have marked those -1 in the two arrays we created, small and great. We marked their first and index element is equal to -1 of small and great arrays respectively. Traversing the array and check if arr[i] is less than or equal to arr[minimum] where minimum we marked as 0, if the condition is found to be true, then update the value of minimum to i, and marked current small array element to -1.

Same thing we will do with the great array, but with from the traversal of the array from the second element of the right side to 0. We will traverse the array and check if arr[i] is greater than or equal to arr[maximum], if it is true then we have to update the value of maximum to 0 and great[i] to -1. Else we will put the maximum as great[i]. After this, we will traverse the array again and check if small[i] and great[i] is not equal to -1, if it is true, then print the mentioned values. ## Code

### C++ code to Find a sorted subsequence of size 3 in linear time

```#include<iostream>
using namespace std;

void getTriplet(int arr[], int n)
{
int maximum = n - 1;
int minimum = 0;
int i;

int* small = new int[n];

small = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}

int* great = new int[n];

great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}

for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
cout << arr[small[i]] << " " << arr[i] << " "<< arr[great[i]];
return;
}
}

delete[] small;
delete[] great;

return;
}
int main()
{
int arr[] = { 11,34,2,5,1,7,4 };
int n = sizeof(arr) / sizeof(arr);
getTriplet(arr, n);
return 0;
}
```
`2 5 7`

### Java Code to Find a sorted subsequence of size 3 in linear time

```class SortedSubsequenceSize3
{
public static void getTriplet(int arr[])
{
int n = arr.length;
int maximum = n - 1;

int minimum = 0;
int i;

int[] small = new int[n];

small = -1;
for (i = 1; i < n; i++)
{
if (arr[i] <= arr[minimum])
{
minimum = i;
small[i] = -1;
}
else
small[i] = minimum;
}
int[] great = new int[n];

great[n - 1] = -1;
for (i = n - 2; i >= 0; i--)
{
if (arr[i] >= arr[maximum])
{
maximum = i;
great[i] = -1;
}
else
great[i] = maximum;
}
for (i = 0; i < n; i++)
{
if (small[i] != -1 && great[i] != -1)
{
System.out.println(arr[small[i]] + " " + arr[i] + " " + arr[great[i]]);
return;
}
}
return;
}
public static void main(String[] args)
{
int arr[] = { 11,34,2,5,1,7,4 };
getTriplet(arr);
}
}
```
`2 5 7`

## Complexity Analysis

### Time Complexity

O(n) where “n” is the number of elements in the array. We have traversed all the array elements. And because the size of the array is N. The time complexity is also linear.

### Space Complexity

O(n) where “n” is the number of elements in the array. We have been storing the smaller and greater element for each array element. Thus the space complexity is also linear.

Translate »