Encodings for Range Minimum Queries over Bounded Alphabets

For the 1D case, any encoding for RMQ requires at least $2n-o(n)$ bits due to its bijective relationship with the Cartesian tree of the input [23]. The best-known result is the $(2n+o(n))$-bit data structure by Fischer and Heun that supports $O(1)$ query time. When the input is highly compressible, one can design data structures whose space usage is parameterized by the compressibility of the Cartesian tree of the input [11, 18] while still supporting queries efficiently. Fischer considered the number of distinct Cartesian trees with bounded alphabets in his Ph.D. thesis (see Section 3.9.1 in [8]) and computed, for each $\sigma \in \{2,3,4\}$, a constant $c_{\sigma }$ such that storing a Cartesian tree constructed from an input of size $n$ over an alphabet of size $\sigma$ requires at least $c_{\sigma }n-\mathrm{\Theta }(1)$ bits.

When the input is an $m\times n$ 2D array with $m\le n$, Demaine et al. [6] showed that there is no Cartesian tree-like structure for the 2D case. Specifically, no structure exists that fully encodes the answers to all queries that can be constructed in linear time. They further showed that when $m=n$, any encoding data structure for answering RMQ queries requires $\mathrm{\Omega }(n^2\log n)$ bits. Since the input array can be trivially encoded using $O(n^2\log n)$ bits (with respect to RMQs), this implies that any encoding data structure uses asymptotically the same space as indexing data structures [24, 3] when $m=\mathrm{\Theta }(n)$. Thus, most of the subsequent results focused on the case where $m=o(n)$.

Brodal et al. [3] proposed an $O(nm\cdot \min (m,\log n))$-bit encoding with $O(1)$ query time. Moreover, they proved that any encoding for answering RMQ requires at least $\mathrm{\Omega }(nm\log m)$ bits. Brodal et al. [2] proposed an asymptotically optimal $O(nm\log m)$-bit encoding for answering RMQ, although the queries are not supported efficiently using this encoding. For $m=o(n)$, the problem of designing a $o(nm\log n)$-bit data structure for a 2D array that answers queries in sublinear time remains an open problem.

For an $m\times n$ 2D array, Golin et al. [13] considered the following four type of queries:

1. 1.

   $1$-sided: $[1,m]\times [1,j]$ for $1\le j\le n$

2. 2.

   $2$-sided: $[1,i]\times [1,j]$ for $1\le i\le m$, $1\le j\le n$

3. 3.

   $3$-sided: $[1,i]\times [j_1,j_2]$ for $1\le i\le m$, $1\le j_1\le j_2\le n$

4. 4.

   $4$-sided: $[i_1,i_2]\times [j_1,j_2]$ for $1\le i_1\le i_2\le m$, $1\le j_1\le j_2\le n$ (any rectangular range).

Golin et al. [13] provided expected upper bounds and matching lower bounds for the encoding space required to answer RMQ for these four query types assuming the elements of the input array are drawn uniformly at random.

(1) Consider a set $ℬ$ containing all possible $m\times n$ arrays where each array has exactly one entry with value $i$ in the $i$-th column, while all other entries are set to $n+1$. The total number of such arrays is $|ℬ|=m^n$. Then, any array $B\in ℬ$ can be reconstructed using 1-sided RMQ on $B$, since the position of the value $i$ in column $i$ is given by $\text{rmq}(1,m,1,i)$. Thus, at least $n\log m$ bits are necessary to answer 1-sided RMQ.
(2) For all indices $j$ such that $j=1$ or $\text{rmq}(1,m,1,j-1)\ne \text{rmq}(1,m,1,j)$, we store the row positions of $\text{rmq}(1,m,1,j)$ using at most $n\lceil \log m\rceil$ bits (in this case, $\text{rmq}(1,m,1,j)$ is in the $j$-th column). Additionally, we maintain a bit string $B$ of size $n$ to mark all such indices $j$, along with an auxiliary structure of $o(n)$ bits that supports rank and select queries on it in $O(1)$ time [20]. Thus, the total size of the data structure is at most $n\log m+O(n)$ bits. To answer $\text{rmq}(1,m,1,i)$ in $O(1)$ time, we proceed as follows: (i) Identify the rightmost $j\le i$ such that $B[j]=1$ using rank and select queries on $B$, and (ii) return $(r,j)$, where $r$ is the stored row position (of $\text{rmq}(1,m,1,j)$) corresponding to the $j$-th column. $◀$

When $A$ is defined over an alphabet of size $\sigma$, there exists at most $\min (\sigma ,n)$ indices $j$ where $\text{rmq}(1,m,1,j-1)\ne \text{rmq}(1,m,1,j)$. Therefore, the data structure of the Theorem 5 takes at most $\min (\sigma ,n)\lceil \log m\rceil +\log \left(\genfrac{}{}{0pt}{}{n}{\min (\sigma ,n)}\right)+o(n)$ bits [20], which is smaller than $n\log m+O(m)$ bits when $\sigma =o(n)$. Furthermore, the following theorem shows that this is optimal when $\sigma \le n$, up to additive lower-order terms (if $\sigma >n$, the data structure of Theorem 5 gives a data structure with optimal space usage).

We use a similar argument as in the proof of (1) in Theorem 5. Let $n\ge j_0>j_1>\mathrm{\cdots }>j_{\sigma -2}\ge 1$ be $\sigma -1$ distinct column positions. Define $ℬ$ as the set of all possible $m\times n$ arrays where: (i) For each $k\in \{0,\mathrm{\dots },\sigma -2\}$, exactly one entry in the $j_k$-th column has the value $k$. (ii) All other entries are set to $\sigma -1$. Since $j_0,\mathrm{\dots },j_{\sigma -1}$ can be chosen arbitrarily within the given range, the total size of $ℬ$ is $m^{\sigma -1}\left(\genfrac{}{}{0pt}{}{n}{\sigma -1}\right)$. Furthermore, any array $B\in ℬ$ can be reconstructed using 1-sided RMQ on $B$. Specifically, for each $k\in \{0,\mathrm{\dots },\sigma -2\}$, the position of the value $k$ is given by $\text{rmq}(1,m,1,j_k^{\prime })$, where $j_k^{\prime }$ is the $k$-th rightmost column such that the column position of $\text{rmq}(1,m,1,j_k^{\prime })$ is $j_k^{\prime }$. $◀$

(1) Let ${ℬ}_i$ be the set of all possible 1D arrays of size $n$ such that for each $B_i\in {ℬ}_i$: (i) $B_i[1]=n\cdot i-1$, and (ii) for $j\in [n]\setminus \{1\}$, $B_i[j]$ is either $B_i[j-1]$ or $B_i[j-1]-1$. The size of ${ℬ}_i$ is $2^{n-1}$. Furthermore, any array $B_i\in {ℬ}_i$ can be reconstructed using $\text{rmq}(1,j)$ for all $j\in [n]$, based on the tie-breaking rule for RMQ.

Next, let $ℬ$ be the set of all possible $m\times n$ arrays where the $i$-th row is an array from ${ℬ}_{m-i}$. The size of $ℬ$ is $2^{m(n-1)}$. Moreover, any array $B\in ℬ$ can be reconstructed using 2-sided RMQ on $B$, since the $i$-th row of $B$ can be determined from $\text{rmq}(1,i,1,j)$ for all $j\in [n]$ (note that $\text{rmq}(1,i,1,j)$ always lies in the $i$-th row by construction - since any element in the first $(i-1)$ rows is larger than every element in the $i$-th row). Thus, at least $\log |ℬ|=\mathrm{\Omega }(mn)$ bits are necessary to answer 2-sided RMQ.
(2) Given an input array $A$, define $m$ distinct 1D arrays $A_1,\mathrm{\dots },A_m$ of size $n$ where for each $i\in [m]$ and $j\in [n]$, $A_i[j]={\min }_{k\in [i]}A[k][j]$. We then construct a data structure to answer RMQ on these arrays in $O(1)$ time on each of these $m$ arrays (we do not store the arrays), using a total of $O(mn)$ bits [9]. Additionally, we maintain $n$ data structures for answering RMQ on each column of $A$ in $O(1)$ time, using another $O(mn)$ bits. To answer the 2-sided RMQ query $\text{rmq}(1,i,1,j)=(i^{\prime },j^{\prime })$, we proceed as follows: (i) Compute $j^{\prime }$ in $O(1)$ time by $\text{rmq}(1,j)$ on $A_i$, and (ii) compute $i^{\prime }$ in $O(1)$ time by $\text{rmq}(1,i)$ on the $j^{\prime }$-th column of $A$. $◀$

Next, consider the case where the input array $A$ is defined over an alphabet $\mathrm{\Sigma }=\{0,\mathrm{\dots },\sigma -1\}$ of size $\sigma$. For each position $(i,j)$, we refer to the range $[1,i]\times [1,j]$ as the 2-sided region defined by $(i,j)$. Let $P$ be a set of all positions in $A$ that serve as answers to some 2-sided RMQ on $A$. For any two positions $(i,j)$ and $(i^{\prime },j^{\prime })$ of $A$, we say that $(i^{\prime },j^{\prime })$ dominates $(i,j)$ if and only if $i\le i^{\prime }$ and $j\le j^{\prime }$. Because of the tie breaking rule, it follows that for any two distinct positions $(i,j)$ and $(i^{\prime },j^{\prime })$ in $P$ if $(i^{\prime },j^{\prime })$ dominates $(i,j)$, then $A[i,j]>A[i^{\prime },j^{\prime }]$. For example in a 2D array in Figure 2(a), two positions $(1,2)$ and $(2,3)$ are in $P$, and since the position $(2,3)$ dominates the position $(1,2)$, $A[1,2]=2$ is greater than $A[2,3]=0$. We partition $P$ into set of staircases $S_0,S_2,\mathrm{\dots },S_{\sigma -1}$ such that for any $\mathrm{\ell }$, $S_{\mathrm{\ell }}$ is a set of all positions $(i,j)$ with $A[i,j]=\mathrm{\ell }$. Then from the definition, we can directly observe the following:

For each $S_{\mathrm{\ell }}$, we define a lattice path $L_{\mathrm{\ell }}$ from $(m+1,0)$ to $(0,n+1)$ that satisfies the following conditions: (i) $L_{\mathrm{\ell }}$ moves only north or east and passes through all positions in $S_{\mathrm{\ell }}$ as its turning points in a clockwise order, and (ii) for any position $(i,j)$ in the array, there exists a position in $S_{\mathrm{\ell }}$ dominated by $(i,j)$ if and only if $(i,j)$ lies on or below $L_{\mathrm{\ell }}$. Moreover, $L_{\mathrm{\ell }}$ can be efficiently encoded from the following lemma:

We can maintain $\sigma$ bitstrings $B_0,\mathrm{\dots },B_{\mathrm{\ell }}$ of Lemma 9 using $\sigma \log \left(\genfrac{}{}{0pt}{}{n+m+2}{m+1}\right)+o(\sigma n)$ bits [20] that support rank and select queries in $O(1)$ time. Given any position $(i,j)$ and $\mathrm{\ell }\in \mathrm{\Sigma }$, we can determine whether the value at $\text{rmq}(1,i,1,j)$ is at most $\mathrm{\ell }$ in $O(1)$ time by Lemma 9 and Proposition 8. Consequently, the 2-sided RMQ $\text{rmq}(1,i,1,j)$ can be answered in $O(\log \sigma )$ time performing a binary search to find the smallest $\mathrm{\ell }$ where $(i,j)$ lies on or below $L_{\mathrm{\ell }}$ After finding such $\mathrm{\ell }$, we report $(m-i^{\prime }+1,j^{\prime })$ as the answer, where $i^{\prime }$ and $j^{\prime }$ denote the number of zeros and ones in $B_{\mathrm{\ell }}$ up to the $j$-th $1$, respectively (i.e., $(m-i^{\prime }+1,j^{\prime })$ is the position in $S_{\mathrm{\ell }}$ dominated by $(i,j)$). Both $i^{\prime }$ and $j^{\prime }$ can be found in $O(1)$ time using rank and select queries on $B_{\mathrm{\ell }}$. We summarize the result in the following theorem.

Note that for any $\sigma =o(m/\log m)$, the data structure of Theorem 10 uses asymptotically less space than the data structure of Theorem 7. Finally, we consider the space lower bound for answering 2-sided RMQ on a 2D array with a bounded alphabet. The following theorem implies that when $\sigma \le n/c$ for any constant $c>4$, the data structure in Theorem 10 achieves asymptotically optimal space usage.

For an $m\times n$ array and $n^{\prime }=n-4\sigma$, we define $\sigma -1$ parallelogram regions $R_{\sigma -2},R_{\sigma -3},\mathrm{\dots },R_0$ from the leftmost part of the array, where each region $R_{\mathrm{\ell }}$ is determined by the four positions: $(1,n^{\prime }+4(\sigma -2-\mathrm{\ell }-1)+1)$, $(1,n^{\prime }+4(\sigma -2-\mathrm{\ell }))$, $(m,4(\sigma -2-\mathrm{\ell }-1)+1)$, and $(m,4(\sigma -2-\mathrm{\ell }))$. For each region $R_{\mathrm{\ell }}$, we construct a staircase $S_{\mathrm{\ell }}$, which consists of the positions in $R_{\mathrm{\ell }}$ whose values are $\mathrm{\ell }$. All other positions in the array are assigned the value $\sigma -1$. Let $𝒜$ be the set of all possible such arrays.

Now, consider two distinct arrays $A_1$ and $A_2$ in $𝒜$ where the staircases $S_{\mathrm{\ell }}$ differ. Denote them as $S_{\mathrm{\ell }}^1$ and $S_{\mathrm{\ell }}^2$, respectively. Without loss of generality, let $(i_1,j_1)$ and $(i_2,j_2)$ be the leftmost positions in $S_{\mathrm{\ell }}^1\setminus S_{\mathrm{\ell }}^2$ and $S_{\mathrm{\ell }}^2\setminus S_{\mathrm{\ell }}^1$, respectively, with . In this case, $(i_1,j_1)$ cannot dominate any positions in $S_{\mathrm{\ell }}^2$, implying that the answers to the query $\text{rmq}(1,i_1,1,j_1)$ on $A_1$ and $A_2$ are different. Consequently, at least $\log |𝒜|$ bits are necessary to answer the 2-sided RMQ on an $m\times n$ array.

To derive a lower bound on the size of $𝒜$, observe that for each region $R_{\mathrm{\ell }}$, we can define a lattice path $L_{\mathrm{\ell }}$ that does not cross the region boundaries. This path starts at the bottom-left corner of $R_{\mathrm{\ell }}$, moves only north or east, and ends at the top-right corner of $R_{\mathrm{\ell }}$. Since each distinct lattice path corresponds to a distinct staircase, defined by the positions of its turning points (in a clockwise order), we obtain at least $\left(\genfrac{}{}{0pt}{}{n-4\sigma }{m}\right)$ possible lattice paths for each region $R_{\mathrm{\ell }}$ [21]. See Figure 2(b) for an example. This implies that $\log |𝒜|$ is at least $\log {\left(\genfrac{}{}{0pt}{}{n-4\sigma }{m}\right)}^{\sigma }=\mathrm{\Omega }(\sigma m\log \frac{n-4\sigma }{m})$. $◀$

We construct the same data structure as in the proof of Theorem 7 (2) using $O(mn)$ bits. To answer the 3-sided RMQ query $\text{rmq}(1,i,j_1,j_2)=(i^{\prime },j^{\prime })$ in $O(1)$ time, we first compute $j^{\prime }$ by $\text{rmq}(j_1,j_2)$ on $A_i$, and compute $i^{\prime }$ by $\text{rmq}(1,i)$ on the $j^{\prime }$-th column of $A$. $◀$ Next, consider the case where the input array $A$ is defined over an alphabet $\mathrm{\Sigma }=\{0,\mathrm{\dots },\sigma -1\}$ of size $\sigma$. For each $k\in \mathrm{\Sigma }$, define a 1D array $C_k$ of size $n$ such that $C_k[j]=i$ where $i$ is the smallest row index such that (i) $A[i][j]=k$ and (ii) all preceding values in the column, $A[1][j],\mathrm{\dots },A[i-1][j]$, are greater than $k$. If $j$-th column does not have the value $k$, set $C_k[j]=m+1$, and if $j$-th column has the value $k$, but does not satisfy the condition (ii), set $C_k[j]=0$. We maintain the arrays $C_0,\mathrm{\dots },C_{\sigma -1}$ along with RMQ data structures that allow queries to be answered in $O(1)$ time, using a total of $n\sigma \log m+O(\sigma n)$ bits [9].

Given a 3-sided range $[1,i]\times [j_1,j_2]$ on $A$ and a value $k\in \mathrm{\Sigma }$, let $j_k$ be the result of $\text{rmq}(j_1,j_2)$ on $C_k$. Then the value $k$ exists in the range if and only if $C_k[j_k]\le i$. Thus, we can determine whether $k$ exists in the range in $O(1)$ time and compute the 3-sided RMQ in $O(\log \sigma )$ time by performing a binary search to find the smallest $k$ that exists in the range. We summarize this result in the following theorem.

Compared to the general case, the above data structure requires less space when $\sigma =o(m/\log m)$, and when $\sigma =O(1)$, it answers 3-sided RMQ in $O(1)$ time.

In the general case, the optimal space data structures for answering 2-sided and 3-sided RMQ require asymptotically the same space by Theorem 7 and Corollary 12. However, when the alphabet size is bounded by $\sigma$, the data structure from Theorem 10 uses asymptotically less space than the data structure of Theorem 13 when $m=o(n)$. Finally, we consider the space lower bound for answering 3-sided RMQ on a 2D array with a bounded alphabet. The following theorem implies that when $\sigma =o(m)$, the data structure in Theorem 13 achieves asymptotically optimal space usage.

(1) Let $𝒞$ be the set of all possible 1D arrays of size $m$ such that for each $C\in 𝒞$: (i) for $k\in \{0,\mathrm{\dots },\sigma -2\}$, $C$ has exactly one occurrence of $k$ at the position $i_k$, (ii) $i_0>i_1>\mathrm{\cdots }>i_{\sigma -2}>1$, and (iii) all other positions have the value $\sigma -1$. Then the size of $𝒞$ is $\left(\genfrac{}{}{0pt}{}{m-1}{\sigma -1}\right)$. Next, let $ℬ$ be the set of all possible $m\times n$ arrays where each column is chosen from $𝒞$. The size of $B$ is ${\left(\genfrac{}{}{0pt}{}{m-1}{\sigma -1}\right)}^n$. Moreover, any array $B\in ℬ$ can be reconstructed using 3-sided RMQ on $B$ since $j$-th column of $B$ can be reconstructed from $\text{rmq}(1,i,j,j)$ for all $i\in [n]$, which proves the theorem. Specifically, for any $k\in \{0,\mathrm{\dots },\sigma -2\}$, the value $k$ appears at $B[i_k][j]$ where $i_k$ is the index of the $k$-th row from the bottom that satisfies $\text{rmq}(1,i,j,j)\ne \text{rmq}(1,i-1,j,j)$. $◀$

Our proof is analogous to the $\mathrm{\Omega }(mn\log m)$-bit lower bound proof of Brodal et al. [3]. First, divide an input array into blocks of size $\sqrt{\sigma }\times 2\sqrt{\sigma }$, and further divide each block into four sub-blocks of size $\frac{\sqrt{\sigma }}{2}\times \sqrt{\sigma }$. Next, assign values to each block using the following procedure:

• $\mathrm{■}$

  Assign the odd values from $\{0,\mathrm{\dots },\sigma -1\}$ to the upper-left sub-block in increasing order, following a row-major order.

• $\mathrm{■}$

  Assign the even values from $\{0,\mathrm{\dots },\sigma -1\}$ to the $\frac{\sqrt{\sigma }}{2}$ anti-diagonals in the bottom-right sub-block, such that the values in each anti-diagonal are larger than those in the anti-diagonals to the right.

• $\mathrm{■}$

  Assign $\sigma$ to all the remaining positions in the block.

Let $𝒜$ be the set of all $m\times n$ arrays where values are assigned according to the above procedure. Since, for any array $A\in 𝒜$, each anti-diagonal within any sub-block of $A$ forms a permutation, and there are $\frac{mn}{2\sigma }$ blocks in $A$, the total size of $𝒜$ is at least ${(\sqrt{\sigma }/2)!}^{\frac{\sqrt{\sigma }}{2}\cdot \frac{mn}{2\sigma }}={(\sqrt{\sigma }/2)!}^{\frac{mn}{4\sqrt{\sigma }}}$. Thus, $\log |𝒜|$ is $\mathrm{\Omega }(mn\log \sigma )$. Now, consider two distinct arrays $A_1$ and $A_2$ in $𝒜$ where . From the assignment procedure, the position $(i_2,j_2)$ lies on an anti-diagonal in the bottom-right sub-block of some block (note that $A_1[i,j]=A_2[i,j]$ for every position $(i,j)$ in the other three sub-blocks of every block). There exists another position $(i_1,j_1)$ in the upper-left sub-block of the same block such that (see Figure 3(a) for an example). Thus, $\text{rmq}(i_1,j_1,i_2,j_2)$ on $A_1$ returns $(i_2,j_2)$, while the same query on $A_2$ returns $(i_1,j_1)$, This implies that at least $|𝒜|$ different $m\times n$ arrays have distinct RMQ answers. $◀$

Theorem 15 implies that if $\sqrt{\sigma }\le \min (m,n/2)$, an $(nm\lceil \log \sigma \rceil +O(mn))$-bit indexing data structure (i.e., a data structure that explicitly stores the input array) of Brodal et al. [3], which answers RMQ in $O(1)$ time, uses asymptotically optimal space for the bounded-alphabet case. This means that in most scenarios, restricting the alphabet size provides little advantage in terms of space efficiency compared to the general case. However, when $\sigma =O(1)$, the $O(mn)$ term in the above indexing data structure of [3] can dominate the space for storing the input. In the following theorem, we show that this can be improved to $o(mn)$ bits while still supporting $O(1)$ query time²²2In fact, the result of [3] provides a trade-offs between index size and query time - if only $o(mn)$-bit space is used for the index, the query time increases to $\omega (1)$..

Let $c=\frac{1}{2}\sqrt{{\log }_{\sigma }mn}$. Then we partition $A$ into blocks of size $c\times c$ and construct the following structures:

• $\mathrm{■}$

  To efficiently handle queries whose range falls entirely within a single block, we store an index data structure from Brodal et al. [3] for each block as follows. We first store a precomputed table of size $2^{O(c^2\log \sigma )}=O({(mn)}^{1/4})$, which contains all possible index structures from [3] for blocks of size $c\times c$. Since each block can be represented as an index into this precomputed table using $\frac{1}{4}\log mn$ bits, the total space required for storing indices of all blocks is $\frac{mn}{4c^2}\cdot \log mn=mn\lceil \log \sigma \rceil$ bits. As we maintain these index structures, we can also access any position in the array in $O(1)$ time.

• $\mathrm{■}$

  Next, we define an auxiliary $m\times n/c$ array $A_r$, where each entry is given by $A_r[i][j]=A[i][j^{\prime }]$, where $j^{\prime }$ is a column position of $\text{rmq}(i,i,(j-1)c+1,jc)$ on $A$. We maintain the index data structure of [3] on $A_r$, using $O(\frac{mn\log \sigma }{c})=o(mn)$ bits. This allows us to access any position in $A_r$ in $O(1)$ time and answer RMQ on $A$ in $O(1)$ time when both the leftmost and rightmost columns of the query range align with block boundaries. Note that the exact column position of the answer can be determined using the RMQ structure on individual blocks.

  Similarly, we define an auxiliary $m/c\times n$ array $A_c$ and maintain the same structure using $o(mn)$ bits so that we can answer RMQ on $A$ in $O(1)$ time when both the topmost and bottommost rows in the query range align with block boundaries.

• $\mathrm{■}$

  Finally, let $A_{rc}$ be an $m/c\times n/c$ array, where each entry is given by $A_{rc}[i][j]=A[i^{\prime }][j^{\prime }]$ where $(i^{\prime },j^{\prime })$ is $\text{rmq}((i-1)c+1,ic,(j-1)c+1,jc)$ on $A$. We maintain the index data structure of [3] on $A_{rc}$ using $O(\frac{mn\log \sigma }{c^2})=o(mn)$ bits. This allows us to access any position in $A_{rc}$ in $O(1)$ time and answer RMQ on $A$ in $O(1)$ time when all boundaries of the query range align with block boundaries.

Any rectangular query range on $A$ can be partitioned into the following regions: (i) at most four rectangular regions fully contained within a single block, (ii) at most two rectangular regions where the leftmost and rightmost columns align with block boundaries, (iii) at most two rectangular regions where the topmost and bottommost rows align with block boundaries, and (iv) at most one rectangular region where all four boundaries align with block boundaries. Using the structures described above, we can determine the position and value of the minimum element in each partitioned region in $O(1)$ time. See Figure 3(b) for an example. The final result is obtained in $O(1)$ time by returning the position of the minimum element among them. $◀$