Algorithm to find three numbers in an array such that a< b < c and v[a]<v[c]<v[b]

Question

Given a vector of integers, I need to find out if there exist three elements a, b, c in the vector such that a < b< c and v[a] < v[c] < v[b].

My approach until now has been the following. First, I forget about a and find for every number in the vector the minimum of the v[i] that lie left of this element. I store this information in another array. Then I apply mergesort and when I reach the point where two elements cross, I test if the right element could be c and the left one b. However, I also need to test if the other elements that cross with the right element could be b, and this increases too much the time complexity. I need it to be linear at most. Could yo give me a hint about how to proceed?

EDIT: Forgive me, the title wasn't OK before. What I need is that a < b < c and v[a] < v[c] < v[b]

EDIT2: Restriction: I cannot use data structures, apart from vectors. And the algorithm has to be based on Divide and Conquer method.

Answer 1

You can do this in O(n) time and worst-case O(n) extra space by iterating over the array while maintaining a stack (a LIFO data structure) of maximal forbidden ranges (v[a], v[c]). The topmost element of the stack is the range from the least value seen so far to the greatest value seen since that least value. (Alternatively, for implementation reasons you may find it easier to keep that range in a separate variable, and only use the stack for older forbidden ranges.)

Processing any individual element can take up to O(n) time (if it has to unwind the entire stack all the way back to the very first range), but this cost is necessarily amortized, such that processing the entire array is still only O(n) time (because the only reason that processing an element would unwind the entire stack is if it's unifying all of the forbidden ranges into one much-larger one, in which case it doesn't need to re-add all of the ranges that it popped, so that work is only done once).