Find all triplets in an array.

Question

Given an array of numbers find all such triplets that satisfy the given condition.

Condition: a[i] < a[j] < a[k] where I < j < k.
Is it possible to do in linear time O(N) ?? if yes how??
if not so what would be optimized approach.

Answer 1

take another array of structure{value,loc}, store initial array's elements in value part of the new array and index as location. Now sort this new array according to value. now scan this new array and check if
arr[i].value < arr[i+1].value < arr[i+2].value and arr[i].loc < arr[i+1].loc < arr[i+2].loc. Print arr[i].value, arr[i+1].value, arr[i+2].value if previous check is true.