Finding a (Small-Big-Medium) subsequence

Question

Given a list of $n$ non repeating integer numbers $L:=(x_1,\dots,x_n)$ develop an algorithm that decides if there are $x_{i_1},x_{i_2},x_{i_3}\in L$ such that $i_1<i_2<i_3$ and $x_{i_1}<x_{i_3}<x_{i_2}$. Only a yes-no answer is required.

The statement also suggest to use the "divide & conquer" strategy.

My try was the following:

I read the vector left to right

• If the list changes from increasing to decreasing, then it is clear that the last read number is lower than the maximum of the currently read list. So if it is greater than the minimum of the current list we can stop. This comparation can be done in $\mathcal{O}(1)$ if we keep track of the minimum of the currently read list.
• If the list changes from decreasing to increasing, then I look for the first number $m$ in the list which is a local minimum and it is lower than the last read number $c$. And then I look for a local maximum appearing after $m$ which is greater than $c$. If both searches are successful we can end. This searches can be done in $\mathcal{O}(\log n)$ time if we keep track of the local maximums and local minimums currently found (binary search).
• If the list keeps increasing we do the same as in the previous step.
• If the list keeps decreasing do nothing.

So the complexity is $\mathcal{O}(n\log n)$. I think the strategy is good, but an online judge rejected it. I don't know if it is due to a silly bug or because the strategy is indeed wrong.

Anyway, seeing the stats of the people who solved the problem, my solution is so memory consumming, so I really think it can be done better.

Any idea?

Answer 1

Your algorithm is wrong in the detail of finding a local maximum after $m$ as pointed out in the comments.

Divide-and-conquer can be used to solve this problem. If such $i_1,i_2,i_3$ exist, there are four cases:

1. $i_1,i_2,i_3\le n/2$, or
2. $i_1,i_2\le n/2$ and $i_3>n/2$, or
3. $i_1\le n/2$ and $i_2,i_3>n/2$, or
4. $i_1,i_2,i_3> n/2$.

Cases 1 and 4 can be checked by solving the sub-problems on $(x_1,\ldots,x_{n/2})$ and $(x_{n/2+1},\ldots,x_n)$. For other cases, numbers less than $\min_{i\le n/2} x_i$ are useless, so we can filter them in $O(n)$ time first. In the following analysis, we assume all numbers are no less than $\min_{i\le n/2} x_i$.

For case 3, $i_1$ can be adjusted to $\arg\min_{i\le n/2} x_i$, then $i_2$ and $i_3$ exist if and only if $x_{n/2+1}<\cdots<x_{n/2}$ does not hold. Therefore we can also check this case in $O(n)$ time.

For case 2, since we have passed case 3, we can assume $x_{n/2+1}<\cdots<x_{n/2}$. Let $r_1=n/2$, and $r_{i+1}$ be the largest index smaller than $r_i$ such that $x_{r_{i+1}}>x_{r_i}$. Similarly let $l_1=1$, and $l_{i+1}$ be the smallest index larger than $l_i$ such that $x_{l_{i+1}}<x_{l_i}$. We mark each element with which sequence its index belongs to. This can be done in $O(n)$ time and space. Easy to see $i_1$ and $i_2$ can be adjusted to $l_s$ and $r_t$ respectively for some $s$ and $t$. Furthermore, we can adjust them such that no $l_j$ or $r_j$ lies between $l_s$ and $r_t$. So we can scan from $x_1$ to $x_{n/2}$ once to get all possible $(i_1,i_2)$ pairs in $O(n)$ time.

For example, suppose $(x_1,\ldots,x_{n/2})=(40,60,30,10,50,20)$, then $\{r_i\}$: $6,5,2$, and $\{l_i\}$: $1,3,4$. We mark these elements as $40_l,60_r,30_l,10_l,50_r,20_r$. Possible $(i_1,i_2)$ pairs are $(40,60)$ and $(10,50)$.

Every possible $(i_1,i_2)$ pair is an open interval. We need to determine whether any of $x_{n/2+1},\ldots,x_n$ falls into these intervals. Note $x_{n/2+1},\ldots,x_n$ are sorted and so are these intervals, we can determine it in $O(n)$ time.

Now checking for case 2 and 3 costs $O(n)$ time and space, so this algorithm costs $O(n\log n)$ time and space in total.