Find a sorted subsequence of size 4 in an array in linear time

Question

We are given an array of numbers and we want to find a subsequence of size 4 that is sorted in increasing order.

for eg ARRAY                :  -4 2 8 3 1 5
sorted subsequence of size 4 : -4 2 3 5

PS:There is a way of finding the sorted subsequence of size 3(see this). I am trying to think along the same lines but can't seem to find a solution for 4 integers.

Answer 1

Having a greater and lesser array is a good option but it increases the space complexity. Below, is a solution to find four numbers in a linear subsequence without additional array space but rather it uses constant space and does only one pass over the array.

#include <iostream>

void sortedSubseqFour(int a[], int n)
{
    int small = INT_MAX;
    int middle_1 = INT_MAX;
    int middle_2 = INT_MAX; 
    int greater = 0;

    int main_small = 0;
    int main_middle_1 = 0;

    int main_main_small = 0;

    for(int i = 0; i<n; i++)
    {
        if (a[i] <= small)
            small = a[i];
        else if (a[i] <= middle_1)
        {
            middle_1 = a[i];
            main_small = small;
        }
        else if (a[i] <= middle_2)
        {
            middle_2 = a[i];
            main_middle_1 = middle_1;
            main_main_small = main_small;
        }
        else
        {
            greater = a[i];
            break;
        }
    }
    //end of loop

    if (greater != 0)
        std::cout << main_main_small << '\t' << main_middle_1 << '\t'
                  << middle_2 << '\t' << greater;
    else
        std::cout << "No such Quadruple";
}

int main()
{
    int arr[10] = {6, 7, 5, 1, 4, 3, 0, 7, 2, 11};
    int n = 10; 

    sortedSubseqFour(arr, n);
    return 0;
}

The above approach remembers all layers of minimum's when it sets the current minimum. The same code can also be used for a sorted subsequence of size 3 in an array by removing main_main_small and middle_2 part of the code.

If, the same code is to be extended up to size k then at say minimum i, we have to remember all minimum's before i, i.e min_1, min_2,... till min_i. Only in the last minimum, i.e. the greatest value in our subsequence, we just break and there is no need to remember previous or current minimum.

Please do inform if any bugs are discovered!

Answer 2

Here is a solution that will find a sorted subsequence of fixed size k+1 by doing k passes over the input. Each pass is done left-to-right.

Pass 1: Create an auxiliary array p1[0..n-1]. p1[i] should store the index j of a number which is smaller than arr[i] and is on the left side of arr[i] (in other words: j<i and arr[j]<arr[i]). p1[i] should contain -1 if there is no such element. (p1 is the same as the smaller array from the solution for size 3).

Pass 2: Create an auxiliary array p2[0..n-1]. p2[i] should store the index j of a number which is smaller than arr[i], is on the left side of arr[i], and such that p1[j] != -1 (in other words: j<i, arr[j]<arr[i], and p1[j]!=-1). p2[i] should contain -1 if there is no such element.

....

Pass k: Create an auxiliary array pk[0..n-1]. pk[i] should store the index j of a number which is smaller than arr[i], is on the left side of arr[i], and such that p(k-1)[j] != -1 (in other words: j<i, arr[j]<arr[i], and p(k-1)[j]!=-1). pk[i] should contain -1 if there is no such element.

After the kth pass, each element where pk[i] != -1 corresponds to the largest element in a sorted subsequence of size k+1.

Pseudocode for kth pass (k>1):

function do_kth_pass(pk[], p_k_minus_1[])
    min = -1
    for i in 0..n-1:
        if min != -1 and arr[i] > arr[min]:
            pk[i] = min
        else
            pk[i] = -1
        if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]):
            min = i

Example:

Index:   0  1  2  3  4  5
Array:  -4  2  8  3  1  5
p1:     -1  0  0  0  0  0
p2:     -1 -1  1  1 -1  4
p3:     -1 -1 -1 -1 -1  3

After 3 passes, you have p3[5] != -1, so a sorted subsequence of size 4 exists. The indices of its elements are: p1[p2[p3[5]]], p2[p3[5]], p3[5], 5 which is 0,1,3,5

Answer 3

You can find the longest increasing subsequence and see if its size if greater than equal to 4(or even k in case you need to find it for a more general question). If the length of the Longest Increasing Subsequence is less than 4(or k) you can report that no such subsequence exists. LIS can be found out in O(nlog(n))