Find any subsequence of magnification with size 3 in an unordered array

Question

I came across a question online: find any subsequence of magnification with size 3 in an unordered array using O (n) time complexity. (just need to return one valid result)

For example: 1 2 0 3 ==> 1 2 3 2 4 7 8 ==> 2 4 7; 4 7 8; 2 4 8 (anyone of them is Okay) 

This is quite relative to the longest subsequence of the increase. But this is also very specific: we just want size 3. I chose the O (N) solution, which requires scanning the array twice.

 The idea: (1) For each element, find is there any one smaller than it on the left side, is there any one larger than it on the right side. (2) We can compute a minimum pre-array and a maximum post-array as pre-processing. For example: 1 2 0 3 ==> minimum pre-array: none 1 1 0 1 2 0 3 ==> maximum post-array: 3 3 3 None 

I am wondering if there are other solutions for this?

Answer 1

Have you tried to find cs.stackexchange?

It is already resolved there: https://cs.stackexchange.com/questions/1071/is-there-an-algorithm-which-finds-sorted-subsequences-of-size-three-in-on-ti

One idea is to do something like an algorithm with the greatest increase in subsequence and does it in one go.

There are several solutions to this question that I have linked.

Answer 2

Here is the solution referenced by this question (in JavaScript)

Comments http://www.geeksforgeeks.org/find-a-sorted-subsequence-of-size-3-in-linear-time/ have other alternative solutions.

 function findIncSeq3(arr) { var hi = Array(arr.length); var lo = Array(arr.length); hi[arr.length - 1] = lo[0] = null; var tmp, i; for (i = arr.length - 2, tmp = arr.length - 1; i >= 0; i--) { if (arr[i] >= arr[tmp]) { tmp = i; hi[i] = null; } else { hi[i] = tmp; } } for (i = 1, tmp = 0; i < arr.length; i++) { if (arr[i] <= arr[tmp]) { tmp = i; lo[i] = null; } else { lo[i] = tmp; } } for(i = 0; i < arr.length; i++) { if(hi[i] !== null && lo[i] != null) { return [arr[lo[i]], arr[i], arr[hi[i]]]; } } return null; } console.log("1,2,5", findIncSeq3([1, 2, 0, 5])); console.log("null", findIncSeq3([5, 4, 3, 2, 1])); console.log("2,3,9", findIncSeq3([10, 8, 6, 4, 2, 5, 3, 9])); 

EDIT Here is one version of the iteration.

 function findIncSeq3(arr) { var tmp = Array(arr.length); for(var i = 0, s = arr.length - 1, lo = 0, hi = arr.length -1; i <= s; i++) { if(s - i !== hi) { if(arr[s - i] >= arr[hi]) { hi = s - i; } else if(tmp[s - i] !== undefined) { return [arr[tmp[s - i]], arr[s - i], arr[hi]]; } else { tmp[s - i] = hi; } } if(i !== lo) { if(arr[i] <= arr[lo]) { lo = i; } else if(tmp[i] !== undefined) { return [arr[lo], arr[i], arr[tmp[i]]]; } else { tmp[i] = lo; } } } return null; }