5
$\begingroup$

Let $A$ be an array of totally ordered elements. A subarray $A[i..j]$ is decreasing if $A[k]\geq A[k+1]$ for all $i \leq k < j$. It is increasing if $A[k]\leq A[k+1]$ for all $i \leq k < j$. It is monotonic if it's either decreasing or increasing.

We call an array is $k$ monotonic if the array can be partitioned into $k$ monotonic subarrays.

Given $A$ a $k$ monotonic array of length $n$, and the value $k$, find the minimum value in the array.

How many comparisons do we need?

If we let $m$ be the maximum number of times a value occurs in $A$, here are some known cases:

$k=1$, then the array is sorted, the minimum is at either end, a $O(1)$ solution.

$k=2$, then we could solve it in $O(m+ \log \frac{n}{m})$, by take the min of two cases.

  • First decrease, then increase, use a $O(m+ \log \frac{n}{m})$ solution. Basically do ternary search unless one find a large segment of equal values, which turns into linear search.
  • First increase, then decrease, just check the boundary values.

$k=n$, then a $O(n)$ time linear search is the best possible.

I believe a $\Omega(m+k \log \frac{n}{k})$ lower bound exists, since even if we are given position for $k/2$ partitions of first decreasing then increasing subarrays, $A_1,\ldots,A_{k/2}$, we still need to spend $O(m_i+\log \frac{|A_i|}{m_i})$ time to search for the minima in each one of them, where $m_i$ is the max number of times a value can appear in $A_i$.

$\endgroup$
  • $\begingroup$ By subarray of length k you mean taking k consecutive elements from the original array? or just taking k elements in (increasing linear) order, in fact I mean you take subsequence or substring? $\endgroup$ – user742 Jul 29 '13 at 13:21
  • $\begingroup$ I mean substring. $\endgroup$ – Chao Xu Jul 29 '13 at 16:09
  • $\begingroup$ @SaeedAmiri, I'm pretty sure this means $k$ consecutive elements, not a subsequence. (I have no idea what substring would mean in this situation.) $\endgroup$ – D.W. Jul 29 '13 at 18:57
  • $\begingroup$ @D.W. Actually I asked from the OP. In the question nowhere mentioned that this is about consecutive elements, and I mentioned this in the comment to OP edit his question to make it more clear for the first glance reading. This type of writing about arrays happens in different situation, so in my opinion should be clear. Also substring and subsequence are very well known, you should know them or read into pattern matching algorithms to find out why they are very important to explicitly mentioning them. And in this case subsequence was a little bit challenging. $\endgroup$ – user742 Jul 30 '13 at 7:58
  • $\begingroup$ @SaeedAmiri, yeah, I am familiar with the meaning and usage of the term "substring". I think whatever is meant by "substring" can be communicated more clearly either by saying "consecutive elements" or by saying "subsequence". In this case I think it is clear enough that the OP is talking about consecutive elements, given his definition of a subarray as $A[i..j]$ (that notation implies consecutive elements) as well as surrounding context and explanations, but if you find this unclear (cont.) $\endgroup$ – D.W. Jul 30 '13 at 8:06
4
$\begingroup$

Here are algorithms and matching lower bounds, which fully resolve the situation:

  • For $k=1$, you can find the minimum in $O(1)$ time: just examine the two endpoints of the array, $A[0]$ and $A[n-1]$.

  • For $k=2$, you can find the minimum in $O(m + \lg (n/m))$ time, as was mentioned in the question. I prove below that you can't do any faster than this (up to a constant factor).

  • For $k\ge 3$, I prove below that finding the minimum takes $\Theta(n)$ time, regardless of $m$ (it takes $\Omega(n)$ time even if you are guaranteed that $m=0$). The trivial algorithm takes $O(n)$ time, so if $k\ge 3$ it is not possible to do better (up to a constant factor) than the trivial algorithm.

Moreover, randomization doesn't help.


Lower bounds. For $k=2$, consider an array $A$ that is positive and strictly decreasing on $A[0\ldots r-1]$, then $A[r]=A[r+1]=\cdots=A[r+m-1]=0$, then is positive and strictly increasing on $A[r+m\ldots n-1]$. Now pick an index $i$ satisfying $r \le i \le r+m-1$, and replace $A[i]$ with $-1$. Notice that this is an array with $k=2$ monotonic sub-arrays (decreasing-then-increasing). However, even if you were given the value of $r$, you would still have to examine every element of $A[r\ldots r+m-1]$ to find the minimum, so any algorithm has to take $\Omega(m)$ time. Moreover, it's easy to show that any algorithm will need $\Omega(\lg n)$ time, so we get a $\Omega(\max(m,\lg n))$ lower bound on the running time. This implies a $\Omega(m + \lg(n/m))$ lower bound as well.

For $k=3$, consider an array that is positive and strictly increasing on $A[0\ldots n-1]$, then pick an index $i$ and modify $A$ by replacing $A[i]$ with $-1$. This is an array with $k=3$ monotonic sub-arrays, and to find the minimum, you have to scan every element of $A$, so the running time is $\Omega(n)$. Notice that in this example, $m=0$, so knowing (an upper bound on) the value of $m$ does not help you speed things up.


If you want a heuristic algorithm for $k=2$ (with no guarantees about worst-case running time), the following randomized algorithm might work well in practice, even though its asymptotic worst-case running time is not any better.

We'll assume the array is decreasing-then-increasing (until you find any evidence to the contrary; if you find evidence that it is decreasing-then-increasing, you can just look at the two endpoints and terminate immediately). We're going to search for the changeover point (which will be the minimum we're looking for). To do that, we'll use ternary search with random selection of the two midpoints.

In particular, we'll use random probing to find two indices $i<j$ such that $A[i],A[j]$ are different from each other and from $A[0],A[n-1]$. Once we have these indices, we can do a case analysis on the relative order of $A[0],A[i],A[j],A[n-1]$ and recurse on either $A[i\ldots n-1]$ or $A[0\ldots j]$. This is a smaller sub-array of expected size $2n/3$.

How long does it take to find two indices $i,j$ that are acceptable? We can start by randomly choosing values for $i$ until $A[i]$ is different from $A[0]$ and $A[n-1]$; then we randomly choose values for $j$ until $A[j]$ is different from $A[0],A[i],A[n-1]$. If there are $m$ repeats, then $n-m$ of the entries are unique; thus, each random choice of $i$ (or $j$) has at least a $(n-m)/n$ probability of finding an acceptable value. Consequently, the expected number of random probes done is $O(n/(n-m))$.

Also, we recurse on an array whose expected size is a constant fraction smaller, so we expect to do only $\lg n$ recursions.

Of course, the total running time could still be bad (e.g., with the example I gave above), but it might often be OK if you have some reason to think the absolute worst-case inputs are unlikely.

$\endgroup$
1
$\begingroup$

For $k>2$, the best algorithm takes $\Omega(n)$ time.

Consider when $A[i] = i$ for all $i$ except $i=j$, and $A[j]=-1$. In this situation, you can't find the minimum without examining every possible $A[i]$.

$\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.