0
$\begingroup$

Imagine a N by M 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively. Is there a efficient algorithm to calculate all the minimum values of each subarray?

[[4, 10, 9, 7],
 [9, 8,  1, 2],
 [1, 21, 3, 1]]

In this example of a 3 by 4 grid, if the two coordinates were (0,1) and (2,2), the minimum in this case would be 1, out of the values 10,9,8,1,21,3.

Other than the naive solution of finding all subsets and calculating the minimum in this subarray, which would be well beyond O(n^4), I have also considered using a method similar to prefix sum by creating a separate 2D array and storing the minimum from (0,0) to (i,j) at the value (i,j), but this issue here is you can't account for the overlap like you do in prefix sums.

Is there a way to account for overlap or another, more efficient algorithm?

Thank you!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-11 Can you also please check the problem statement? In particular, I don't understand where "finding all subsets and calculating the minimum in this subarray" comes from. What are "subsets"? $\endgroup$ Commented Feb 27, 2021 at 22:14
  • $\begingroup$ I changed the wording to find all minimums. The problem asks for the minimums of all subarrays. $\endgroup$ Commented Feb 27, 2021 at 22:22
  • 2
    $\begingroup$ Then you can use dynamic programming. Let $get(i_1, j_1, i_2, j_2)$ be an answer for the corresponding rectangle. Then $get(i_1, j_1, i_2, j_2) = \min(get(i_1, j_1, i_2 - 1, j_2), get(i_1, j_1, i_2, j_2 - 1), a[i_2, j_2])$. You can draw these rectangles to understand why. $\endgroup$ Commented Feb 27, 2021 at 22:37
  • $\begingroup$ @Dmitry, I believe you ave leaving out parts of the respective row/column in your recurrence. $\endgroup$ Commented Mar 2, 2021 at 15:46
  • $\begingroup$ @vonbrand, what do you mean? $\endgroup$ Commented Mar 2, 2021 at 19:25

1 Answer 1

Reset to default
1
$\begingroup$

In one dimension, looking for the maximum sum, this is solved by Kadane's algorithm. The referenced page does discuss some of the history and gives pointers to efficient solutions for the two-dimensional problem.

Bentley in his seventh "Programming Pearls" column (see e.g. here) discusses the one-dimensional problem in depth, devising ever more efficient algorithms for it's solution. Bentley's columns (and much more) are collected in his book "Programming Pearls" (Addison-Wesley, 2nd edition 1999).

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.