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!
-
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– user1149662021年02月27日 22:14:46 +00:00Commented 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$Steven Smith– Steven Smith2021年02月27日 22:22:52 +00:00Commented 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$user114966– user1149662021年02月27日 22:37:30 +00:00Commented Feb 27, 2021 at 22:37
-
$\begingroup$ @Dmitry, I believe you ave leaving out parts of the respective row/column in your recurrence. $\endgroup$vonbrand– vonbrand2021年03月02日 15:46:02 +00:00Commented Mar 2, 2021 at 15:46
-
$\begingroup$ @vonbrand, what do you mean? $\endgroup$user114966– user1149662021年03月02日 19:25:25 +00:00Commented Mar 2, 2021 at 19:25
1 Answer 1
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).