4
$\begingroup$

Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs?

More formally, answering the query

$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$

In terms of preprocessing, and answering the query where the array is static

$\endgroup$

1 Answer 1

2
$\begingroup$

This can be reduced to rectangular RMQ in $O(n^2)$ time and space. Create a new array $H$ where $H[i][i+j] := G[i][j]$, padding entries $H[i][k]$ with $k < i$ or $k \ge i + n$ with $\infty$. Run $RMQ(a, b, c, d)$ on $H$ whenever you would run $RMQ_P(a, b, c, d)$ on $G$.

Now run your favorite 2D-RMQ algorithm such as this. Perhaps you want to be very conservative with the extra space used though. In that case I suspect unpacking your favorite result will show that it helps to avoid writing $H$ down, and instead use an $O(1)$ function to produce values of $H$ by lookup into $G$.

$\endgroup$
1
  • $\begingroup$ Thanks, this works very nicely. I wrote some Python code: repl.it/repls/TransparentExaltedAngle that tested this on a 10x10 grid of random integers on all possible queries $(a,b,c,d)$ and it passed all tests. Thanks! $\endgroup$ Commented Aug 13, 2019 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.