Find a sorted subsequence of size 3 in linear time in Python\\n

Suppose we have an array with N numbers, we have to check whether the 3 elements such that b[i]< b[j] < b[k] and i < j < k in linear (O(n)) time. If there are multiple such triplets, then print any one of them.

So, if the input is like [13, 12, 11, 6, 7, 3, 31], then the output will be [6,7,31]

To solve this, we will follow these steps −

• n := size of A
• maximum := n-1, minimum := 0
• smaller := an array of size 1000, and fill with 0
• smaller[0] := -1
• for i in range 1 to n, do
  • if A[i] <= A[minimum], then
    • minimum := i
    • smaller[i] := -1
  • otherwise,
    • smaller[i] := minimum
• greater := an array of size 1000, and fill with 0
• greater[n-1] := -1
• for i in range n-2 to -1, decrease by 1, do
  • if A[i] >= A[maximum], then
    • maximum := i
    • greater[i] := -1
  • otherwise,
    • greater[i] := maximum
• for i in range 0 to n, do
  • if smaller[i] is not same as -1 and greater[i] is not same as -1, then
    • return A[smaller[i]], A[i], A[greater[i]]
• return "Nothing"

Example

Let us see the following implementation to get better understanding −

 Live Demo

def find_inc_seq(A):    n = len(A)    maximum = n-1    minimum = 0    smaller = [0]*10000    smaller[0] = -1    for i in range(1, n):       if (A[i] <= A[minimum]):          minimum = i          smaller[i] = -1       else:          smaller[i] = minimum    greater = [0]*10000    greater[n-1] = -1    for i in range(n-2, -1, -1):       if (A[i] >= A[maximum]):          maximum = i          greater[i] = -1       else:          greater[i] = maximum    for i in range(0, n):       if smaller[i] != -1 and greater[i] != -1:          return A[smaller[i]], A[i], A[greater[i]]    return "Nothing" arr = [13, 12, 11, 6, 7, 3, 31] print(find_inc_seq(arr) )

Input

[13, 12, 11, 6, 7, 3, 31]

Output

(6, 7, 31)