0
$\begingroup$

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

Thanks in advance.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Where is your question? "I have trouble understanding ... the following question". Should I explain what is "a 2D array"? Should I explain "coordinates"? The points is, if you cannot indicate where or how you have trouble, we have even more trouble helping you. $\endgroup$ – John L. Mar 3 '19 at 11:32
  • 1
    $\begingroup$ "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? $\endgroup$ – John L. Mar 3 '19 at 11:55
  • $\begingroup$ 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. $\endgroup$ – Liel Fridman Mar 3 '19 at 12:04
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W.♦ Mar 3 '19 at 19:30
  • $\begingroup$ 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? $\endgroup$ – D.W.♦ Mar 3 '19 at 19:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.