Given an array consisting of integers. Print all the sub-sequences based on 132 pattern that is, for i<j<k print all the sub-sequences such that arr[i]<arr[k]<arr[j].

Time Complexity: O(n).

Space Complexity: O(n).

Given an array consisting of integers. Print all the sub-sequences based on 132 pattern that is, for i<j<k print all the sub-sequences such that arr[i]<arr[k]<arr[j].

Time Complexity: O(n).

Space Complexity: O(n).

are you sure time complexity is O(n) ? leave the calulation part ,ouput of all such subsquence will take more than O(n) or may be question is not to print subsquence but to find how many sub subsquence exist?.

Can we even find the number of such elements in O(n)