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, which is sorted in ascending order.

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

PS: There is a way to find a sorted subsequence of size 3 ( see this ). I try to think in the same directions, but cannot find a solution for 4 integers.

Answer 1

Here is a solution that finds a sorted subsequence of a fixed size k+1 by doing k , going through the input. Each pass runs from left to right.

Pass 1: create an auxiliary array p1[0..n-1] . p1[i] must store the index j number that is less than arr[i] and is located on the left side of arr[i] (in other words: j<i and arr[j]<arr[i] ). p1[i] must contain -1 if there is no such element. ( p1 matches the smaller array from the solution for size 3).

Pass 2: create an auxiliary array p2[0..n-1] . p2[i] must store the index j number smaller than arr[i] located 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] must contain -1 if there is no such element.

....

Pass k: Create an auxiliary array pk[0..n-1] . pk[i] must store the index j number smaller than arr[i] , located 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] must contain -1 if there is no such element.

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

Pseudocode for k th 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 there is a sorted subsequence of size 4. The indices of its elements are: p1[p2[p3[5]]], p2[p3[5]], p3[5], 5 , which is equal to 0,1,3,5

Answer 2

Having a larger and smaller array is a good option, but it increases the complexity of the space. Below is the solution to find four numbers in a linear subsequence without additional array space, but instead it uses constant space and skips only one array.

 #include<iostream> using namespace std; int 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) { cout<<"\n"<<main_main_small<<"\t"<<main_middle_1<<"\t" <<middle_2<<"\t"<<greater<<"\n"; } else cout<<"\n No such Quadruple"; return 1; } int main() { int arr[20] = {6,7,5,1,4,3,0,7,2,11}; int n = 10; sortedSubseqFour(arr,n); return 0; } 

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

If, the same code should be expanded to the size of 'k', then, say, minimum i, we must remember all the minimums to i, (ie) min_1, min_2, ... to min_i. Only in the last minimum (ie), the largest value in our subsequence, we simply break, and there is no need to remember the previous or current minimum.

Please report if any errors are found!

Answer 3

You can find the longest increasing subsequence and see if its size if it is greater than 4 (or even k if you need to find it for a more general question). If the length of the longest growing subsequence is less than 4 (or k), you can report that such a subsequence does not exist. LIS can be found in O(nlog(n))

Answer 4

Create an array of smaller and greater , similar to what was done for a subsequence of size 3. In addition to this, it also has an betweenSmallerAndCurrent array that stores the index of the value that is between the smallest and the current element - both by value and by index. More specific:

 betweenSmallerAndCurrent[i] = -1 or input[smaller[i]] < input[betweenSmallerAndCurrent[i]] < input[value[i]] and smaller[i] < betweenSmallerAndCurrent[i] < value[i] 

Building this should be fairly simple.

You simply return the index i , where everything betweenSmallerAndCurrent[i] , smaller[betweenSmallerAndCurrent[i]] and greater[i] all initialized. Note that we cannot just check smaller[i] , because we may have something like [2,3,1,4,5] , and in this case, when we go to 4 , the second smallest value is 3 is up to the current smallest value of 1 .

Example:

 Indices: 0 1 2 3 4 5 6 7 Input: 12 11 10 5 6 2 9 30 smaller: -1 -1 -1 -1 3 -1 5 5 betweenSmallerAndCurrent: -1 -1 -1 -1 -1 -1 4 4 greater: 7 7 7 7 7 7 7 -1 

The only index with all initialized values ​​is 6 (input value 9).

Java code: (not tested)

 void find4Numbers(int arr[], int n) { int max = n-1; //Index of maximum element from right side int min = 0, second = -1; //Index of minimum element from left side int i; // Create an array that will store index of a smaller // element on left side. If there is no smaller element // on left side, then smaller[i] will be -1. int[] smaller = new int[n]; int[] betweenSmallerAndCurrent = new int[n]; smaller[0] = -1; // first entry will always be -1 betweenSmallerAndCurrent[0] = -1; for (i = 1; i < n; i++) { if (arr[i] <= arr[min]) { min = i; smaller[i] = -1; betweenSmallerAndCurrent[i] = -1; } else { smaller[i] = min; if (second != -1 && arr[second] < arr[i]) betweenSmallerAndCurrent[i] = second; else betweenSmallerAndCurrent[i] = -1; if (second == -1 || arr[i] < arr[second]) second = i; } } // Create another array that will store index of a // greater element on right side. If there is no greater // element on right side, then greater[i] will be -1. int[] greater = new int[n]; greater[n-1] = -1; // last entry will always be -1 for (i = n-2; i >= 0; i--) { if (arr[i] >= arr[max]) { max = i; greater[i] = -1; } else greater[i] = max; } // Make sure they're right System.out.println(Arrays.toString(smaller)); System.out.println(Arrays.toString(betweenSmallerAndCurrent)); System.out.println(Arrays.toString(greater)); // Now find a number which has both a greater number on // right side and smaller number on left side for (i = 0; i < n; i++) { if (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1) { System.out.printf("%d %d %d %d\n", arr[smaller[betweenSmallerAndCurrent[i]]], arr[betweenSmallerAndCurrent[i]], arr[i], arr[greater[i]]); return; } } // If we reach number, then there are no such 3 numbers System.out.println("No such triplet found"); } 

You may notice that the main code changes from this , besides C and Java conversion and added initializations, it is in a loop that sets up smaller . The code should be pretty straightforward - try translating it into words if you have any problems.

Test .

Answer 5

For each element, find the next larger element index else -1 Now think of it as a graph and find a path of length k (if it exists) This can be done easily in linear time using hashtable and memoization.