array median transformation using the min number of steps

Question

Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$.

I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\max,\max,\max,\max,\dots,\max]$.

In one step, I can apply the following operation to any consecutive sub-array $A[x..y]$:

Assign to all $A[i]$ with $x \leq i \leq y$ the median of subarray $A[x..y]$.

We consider as median always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.

What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.

---

Example 1:

Let $A = [1, 2, 3]$. We need to change it to $[3, 3, 3]$. The minium number of steps is two, first for subarray $A[2..3]$ (after that $A$ equals to $[1, 3, 3]$), then operation to $A[1..3]$.

Example 2:

$A=[2,1,1,2]$.The min step is two. The median of subarray $A[1..4]$ is $2$ (3rd element in $[1,1,2,2]$. Apply the operation to $A[1..4]$ once and we get $[2,2,2,2]$.

Answer 1

In the comments, Wu Yin claimed an upper bound of $\lceil \log_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A[x,y]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A[i,i+1]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

Algorithm:

Let $step(x,y)$ denote an operation on the subarray $A[x,y]$ as is defined in the question.

• Perform $step(i,i+1)$ for all $0\leq i < N$. After that, there is some 2-length subarray containing only $\max$.

• Perform $step(i,i+3)$ for all $0\leq i < N-3$. After that, there is some 4-length subarray filled with $\max$.

• Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.

Running Time:

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.