2
$\begingroup$

I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<A[i+1]$).

There are 2 restrictions:

  • Only $O(\sqrt{n})$ additional space (rather than $O(n)$ which is used for the regular RMQ d.s. Also see here)

  • Only a constant number of entry readings from the original array while answering a query

I thought of a solution that uses $\log(n)\log\log(n)$ space. Which is $< \sqrt{n}$ for $n>1165$ according to wolframalpha. (as @jbapple said, $\log(n)\log\log(n)=O(\sqrt{n})$ so that's fine)

edit: i found an error in the solution: in part 3, each item needs to know which section it belongs to (or at least the closest local min to it) - that's already $O(n)$ additional space.

However, i won't delete it so maybe it can be modified to a correct solution

My solution:

Find all local minimums and save pointers to them in $O(n)$ time, $O(\log n)$ space $(<\sqrt{n}\space)$ .

Apply regular RMQ on $\log(n)$ local minimums (powers of $2$ technique - section 3.3 page 5 in this paper). This takes $n\log(n)$ space, but $n$ in my case is $\log(n)$ (number of "representatives"), so it'll cost $\log(n)\log\log(n)$ space only. This is for part 3 - see ahead.

Answering a query:

There are 3 types of queries:

  1. Range begins just after a local minimum and ends just after the next one: local min to local min This is easily solved in $O(1)$ since it's either the leftmost or rightmost entry
  2. Range between 2 local mins (not including): inside Also easy (same method)
  3. Overlapping range: overlapping This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

    • Sections of "local min to local min" can be solved in $O(1)$ using the regular RMQ we built above.
    • Regarding the other 2 sections, for each of them we can determine the min in $O(1)$ (must be either leftmost or rightmost item).
    • Finally we're left with exactly 3 numbers. Get their min in $O(1)$
$\endgroup$
  • 3
    $\begingroup$ I haven't read your solution, but I did read your intro, in which you claim to have a $\log n \log \log n$ solution, but you are in search of a $O(\sqrt{n})$ solution. Good news! $\log n \log \log n \in O(\sqrt{n})$! Just check out your definition of big-O more carefully. $\endgroup$ – jbapple Aug 31 '14 at 18:07
  • 1
    $\begingroup$ Or, if you want no more than exactly $\sqrt{n}$ space usage but "Only a constant number of entry readings from the original array while answering a query", just let that constant go to 1165, the point at which $\log n \log \log n < \sqrt{n}$ and use brute force for arrays smaller than that. $\endgroup$ – jbapple Aug 31 '14 at 18:12
  • $\begingroup$ Wonderful! Except that makes me think i got some mistake in my solution... $\endgroup$ – Alaa M. Aug 31 '14 at 19:14
  • $\begingroup$ If you want us to check whether your algorithm is correct: This site is not well suited for "please check whether my answer is correct" questions; only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. $\endgroup$ – D.W. Aug 31 '14 at 19:43
  • 2
    $\begingroup$ @AlaaM. "only for $n>1165$" is not a restriction, when talking about $O$-classes. So you are asking for something you already have. $\endgroup$ – FrankW Sep 1 '14 at 12:51
0
$\begingroup$

Here's how it works:

I'll provide 2 solutions:

  1. $O(\log{n})$ space and $O(\log{\log{n}})$ query.
  2. $O(\log{n})$ space and $O(\log{\log{\log{n}}})$ query.

1) Using binary search on local mins.

Find all local minimums and store them in an array $B$ in their original order - $O(n)$ time, $O(\log{n})$ space ($<O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.) To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we binary-search the array $B$ for indices $i$ and $j$ to find the closest index which has a local_min.

Answering a query:

There are 3 types of queries:

  1. Range begins just after a local minimum and ends just after the next one:

block

First, we need to recognize we’re in this case. Perform a binary search on array $B$ for index $j$ or the smallest index larger than $j$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{n}})$.

  1. Range between 2 local mins (not including):

Same method as above, but this time we’ll find $i-2$ and $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(loglogn)$.

inside block

  1. Overlapping range:

overlapping

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture). Again, to recognize the case, binary-search for $i,j$ in $B$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and i overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ, compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{n}})$.

2) Using y-fast trie on local mins.

Find all local minimums and store them in a y-fast trie structure (call it $Y$) and let the keys be the original indices - $O(n)$ time, $O(\log{n})$ space. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.) To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we search $Y$ for indices $i$ and $j$ (or their pred and succ) to find the closest index which has a local_min. Search of pred/succ in a y-fast-trie of $n$ elements takes $O(\log{\log{n}})$.

Answering a query:

There are 3 types of queries:

  1. Range begins just after a local minimum and ends just after the next one:

block

First, we need to recognize we’re in this case. Search for index $j$ or its successor in $Y$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{\log{n}}})$.

  1. Range between 2 local mins (not including):

inside block

Same method as above, but this time we’ll find $i-2$ and $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(\log{\log{\log{n}}})$.

  1. Overlapping range:

overlapping

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Again, to recognize the case, search for $i,j$ in $Y$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and $i$ overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ , compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{\log{n}}})$.

Proof for cases 1&2:

Theorem: in this type of ranges, the min is either the leftmost or rightmost entry. Proof by contradiction: Suppose the min is somewhere inside the block, and not at the edges. If it’s the min then it’s smaller than both its left and right neighbors. Thus it’s a local_min by definition. This is a contradiction because we assumed we have a block from a local_min to the next local_min (no local_mins’s in between).

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