Given an array of distinct numbers, we have to find if there is any triplet of type (A[i], A[j], A[k]) such that A[i] < A[j] < A[k] and i < j < k.
For example consider the array {6, 1, 5, 2, 4}
We have a triplet {1, 2, 4} which satisfies the given criteria.
Where as the array {4, 1, 5, 3, 2} does not have any such triplets.
Simple algorithm:
For each element we can try to find the lesser element to the left of it and find the greater element to the right of it. This will obviously give the required result. But this algorithms in O(n2).
printIncreasingTriplet1() method implements this approach.
Linear time algorithm:
We declare two arrays leftMin and rightMax. leftMin stores the minimum element seen so far up to the given index. Similarly rightMax stores the maximum element seen so far up to the given index but from reverse order.
We are essentially calculating the lesser elements to the left and greater elements to it’s right for each element. In the next step we need not search for the lesser and greater elements for all elements. They are simply available in leftMin and rightMax at the same index.
printIncreasigTriplet2() in the code implements this approach. This runs in O(n) time and takes O(n) space.