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!

$\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$
    – user114966
    Feb 27 at 22:14
  • $\begingroup$ I changed the wording to find all minimums. The problem asks for the minimums of all subarrays. $\endgroup$ Feb 27 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$
    – user114966
    Feb 27 at 22:37
  • $\begingroup$ @Dmitry, I believe you ave leaving out parts of the respective row/column in your recurrence. $\endgroup$
    – vonbrand
    Mar 2 at 15:46
  • $\begingroup$ @vonbrand, what do you mean? $\endgroup$
    – user114966
    Mar 2 at 19:25
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).

$\endgroup$

Your Answer

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

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