# Two-dimensional Range Minimum Query under a constraint

So, I have trouble understanding and solving the following question:

You are given a 2D array. Design an algorithm that, given two coordinates (each with two indexes ofc), returns the minimum in the rectangle between those coordinates. You know that the number of lines in that rectangle (of each query) is greater than $$\frac{n}{3}$$. Preparation time should be $$O(n^2)$$ and query time should be $$O(1)$$.

• "the number of lines ... is greater than $\frac n3$." Is the number of lines the sum of the number of rows and the number of columns? What is $n$? the number of rows? the number of columns? their product? the larger of the two? – John L. Mar 3 '19 at 11:55
• The task was to design an algorithm that meets all those constraints. The number of lines is the number of rows and $n$ is the number of rows and the number of columns. Sorry for that and thanks again. – Liel Fridman Mar 3 '19 at 12:04
• Also, what is $n$? What is meant by "the number of lines" of a portion of an array? Can you credit the original source of the problem? – D.W. Mar 3 '19 at 19:30