Search for minimum in an array of $k$ monotonic subarrays

Question

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

Answer 1

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.

Answer 2

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