Find A Sorted Subsequence Of Size 3 In Linear Time In C++

In this guide, you will discover the process of locating a sorted subsequence of size 3 efficiently within C++ in a linear time complexity.

The problem statement is as follows:

Identify a set of three elements in an array of numerical values, with the requirement that these elements must form a subsequence where they are sorted in ascending order and located at increasing indices within the array. This particular subsequence consists of three numbers found at positions denoted by i, j, and k in the array named nums.

nums[i] < nums[j] < nums[k]

i < j < k

Solution for the above question (method 1):

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
vector<int> findSortedSubsequence(vector<int>& nums) {
 int n = nums.size();
 if (n < 3) {
 return {};
 }
 int small = numeric_limits<int>::max();
 int large = numeric_limits<int>::max();
 int index_small = -1;
 for (int i = 0; i < n; ++i) {
 if (nums[i] <= small) {
 small = nums[i];
 index_small = i;
 } else if (nums[i] <= large) {
 large = nums[i];
 } else {
 vector<int> result = {small, large, nums[i]};
 return result;
 }
 }
 return {};
}
int main() {
 int n=0;
 cout << "Enter length of array" << endl;
 cin >> n;
 vector<int> nums;
 cout << "Enter the array elements" << endl;
 for(int i=0; i<n; i++){
 int temp=0;
 cin >> temp;
 nums.push_back(temp);
 }
 vector<int> result = findSortedSubsequence(nums);
 
 if (result.size() == 3) {
 cout << "Sorted subsequence of size 3 found: ";
 for (int num : result) {
 cout << num << " ";
 }
 cout << endl;
 } else {
 cout << "No sorted subsequence of size 3 found." << endl;
 }
 
 return 0;
}

Output:

The variables present in the program are:

• ✅ "n" which indicates the length of the array or number of elements present in the array.
• ✅ "nums" is the vector where all the elements are stored.
• ✅ The "small" variable is used to track the smallest element in the array.
• ✅ The "large" variable is used to track the second smallest element in the array.
• ✅ "index_small" is used to store the index of small.
• ✅ "result" is the vector where the subsequence is stored.

The functions implemented in the software are:

• ✅ retrieveOrderedSubsequence: This specific function accepts the vector nums as input and provides the output.
• ✅ initialize: This particular function serves as the entry point for the program.

Explanation:

• ✅ In this example, the first lines for the user inputs and storing them in a vector.
• ✅ In the function, it checks whether the length of the input vector is greater or equal to three if it is less than three, it return an empty vector because we cannot form the subsequence of three elements.
• ✅ After that, we initialize the small and large to maximum possible integer value and initialize the small_index to -1.
• ✅ If the current element is smaller than or equal to small, it updates small to the current element and sets index_small to the current index.
• ✅ If the current element is greater than small but smaller than or equal to large, it updates large to the current element.
• ✅ If the current element is greater than both small and large, it means a sorted subsequence of size 3 is found. The function creates a result vector containing small, large, and the current element, and returns this vector.

Solution for the above question (method 2):

#include <iostream>
#include <vector>
using namespace std;
void findSortedSubsequence (vector<int>& nums) {
 int n = nums.size();
 if (n < 3) {
 cout << "No such triplet found";
 return;
 }
 int max = n - 1;
 int min = 0;
 int i;
 vector<int> left_array(n, -1);
 vector<int> right_array(n, -1);
 for (i = 1; i < n; i++) {
 if (nums[i] <= nums[min]) {
 min = i;
 left_array[i] = -1;
 } else {
 left_array[i] = min;
 }
 }
 for (i = n - 2; i >= 0; i--) {
 if (nums[i] >= nums[max]) {
 max = i;
 right_array[i] = -1;
 } else {
 right_array[i] = max;
 }
 }
 for (i = 0; i < n; i++) {
 if (left_array[i] != -1 && right_array[i] != -1) {
 cout << nums[left_array[i]] << " " << nums[i] << " " << nums[right_array[i]];
 return;
 }
 }
 cout << "No such triplet found";
}

int main() {
 int n=0;
 cout << "Enter length of array" << endl;
 cin >> n;
 vector<int> nums;
 cout << "Enter the array elements" << endl;
 for(int i=0; i<n; i++){
 int temp=0;
 cin >> temp;
 nums.push_back(temp);
 }
 findSortedSubsequence (nums);
 return 0;
}

Output:

The variables present in the function are:

• ✅ In this example, the "n" is to indicate the number of elements present in the vector.
• ✅ "nums" name of the input vector.
• ✅ "max" stores the index of the maximum element of the right side of the array.
• ✅ "min" stores the index of the minimum element of the left side of the array.
• ✅ "i" variable used for iterating.
• ✅ "left_array" vector will store the index of the smallest element up to that particular index.
• ✅ "right_array" stores the index of the greater element on the right side of each element in nums.

Functions used in the above program are:

• ✅ findSortedSubsequence: This function will return nothing but takes the input vector.
• ✅ In this function, only two different vectors are used to get the result.
• ✅ main: It is the main function that starts the execution.

Explanation:

• ✅ It constructs left_array , storing indices of smaller elements on the left.
• ✅ It constructs right_array , storing indices of greater elements on the right.
• ✅ The function iterates through the array and checks for left and right elements.
• ✅ If found, it prints the triplet and exits.
• ✅ If no triplet is found, it prints "No such triplet found" .
• ✅ Handles cases where the input array has less than 3 elements, providing an appropriate message.