1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Nice problem. May I ask you where it comes from? $\endgroup$ – Leo163 Mar 17 '18 at 22:07
  • 1
    $\begingroup$ Of course, it comes from here aceptaelreto.com/problem/statement.php?id=384 $\endgroup$ – Álvaro G. Tenorio Mar 17 '18 at 22:16
  • 1
    $\begingroup$ Could you please explain more on how to search $m$ and $c$ in $O(\log n)$ time? $\endgroup$ – xskxzr Mar 18 '18 at 4:02
  • $\begingroup$ We keep track of the local minimums currently found and store them in a binary search tree, being the "key" the value of the minimum, and the "value" the smallest position in the list of the local minimums lower than the current minimum (take into acount that when we insert a local minimum, its position in the list is the highest, so to compute the "value" we just need to look to the value of the previous key in the tree). This will take $\mathcal{O}(\log n)$ time. $\endgroup$ – Álvaro G. Tenorio Mar 18 '18 at 7:32
  • 1
    $\begingroup$ I don't understand how your global pointer works. For example, for local maximums {2,3,1}, when you insert 3, you do not update the value of 2, then after 1 is inserted, how do you find the real value of 2? $\endgroup$ – xskxzr Mar 18 '18 at 11:00
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.