# Finding the minimum value of all subsets in a 2D array

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!

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