# Complexity of Parallelogram Range Minimum Query

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

$$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$$
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$$.
• 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! Commented Aug 13, 2019 at 11:03