The sum of the maximum value of a rectangular area not exceeding K

Posted on Edited on In Waline:

Today’s question of the day by leetcode is a difficult question, but I summarize it not because of its difficulty, but because it is a combination of a variant of the prefix and and a binary search tree, which can help me review.

The first is the title link: https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/

Violence enumeration

First of all, it is easy to think of brute force enumeration of all submatrices, then the complexity at this time is O (m ^ 2 * n ^ 2), which is easy to timeout. But this is the basic idea, let’s optimize step by step

Naive two-dimensional prefix sum

In the process of brute force enumeration, we have actually done many calculations.

We can define sum [i] [j] as the sum of all cell values from (0,0) to (i, j)

那么，sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i][j]

Therefore, when we require (x1, y1) as the sum of the regions in the upper left corner and (x2, y2) as the sum of the regions in the lower right corner, we can directly use the prefix and array to quickly solve:

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

In this way, we can first initialize the prefix and array through O (m * n), and then calculate the sum of all submatrices through O (m * n), thus reducing the time complexity to O (m * n);

Main problem-solving ideas (two-dimensional prefix and abstraction are one-dimensional)

Let’s consider how the solution of “naive two-dimensional prefix sum” searches for the answer (submatrix): uniquely determine a matrix by enumerating “upper left corner” & “lower right corner”.

In other words, the four edges of the sub-matrix are uniquely determined by enumerating (i, j) (i, j) and (p, q) (p, q), and each coordinate point can be regarded as a certain edge of the sub-matrix.

Since there are four sides to determine, how can we reduce the complexity?

We can enumerate three of the edges and then use the data structure to speed up finding the fourth edge.

Once we have identified the three edges (red), the resulting submatrix simply depends on the position of the fourth edge (yellow):

So the problem becomes "how to quickly find the position of the fourth edge (yellow) ".

We can further narrow down the problem by considering the case where the matrix has only one row (one dimension):

At this time, the problem is further transformed into “In a one-dimensional array, solve for the sum of the largest contiguous subarrays that do not exceed K.”

How to do this step?

The current value in the original one-dimensional array (not the prefix and array) is the sum of all cells in the column between the upper and lower boundaries

For this one-dimensional problem, we can first preprocess the “prefix sum”, then enumerate the left endpoint of the subarray, and then solve the position of its right endpoint by “binary”.

Assuming we have obtained the prefix and sum of a one-dimensional array, we can obtain the sum of the subscript range [i, j] [i, j]:
areaSum(i,j)=sum[j]−sum[i−1]⩽k

After the transformation:
sum[j]⩽k+sum[i−1]

We have two ways to maximize areaSum (i, j):

  • Determine (enumerate) the left endpoint position i, and find the largest right endpoint sum [j] that matches the condition.
  • Determine (enumerate) the position j of the right endpoint, and find the smallest left endpoint that matches the condition sum [i]

For a one-dimensional array without negative weights, we can enumerate the left endpoint i, and at the same time use the “monotonically increasing” feature of the prefix sum to find the largest sum that meets the condition of sum [j] k + sum [i − 1] through “binary”. Value sum [j] to solve the answer.

However, if it has negative weights, the prefix sum will lose its “monotonically increasing” characteristic, and we cannot use the enumeration i combined with the “binary” to find j.

At this time, the process needs to be reversed: we enumerate j from left to right, and use the “ordered set” structure to maintain the traversed position, find the sum [i] sum [j] − k sum [i] condition The smallest value sum [i] solves the answer.

Based on the above analysis, the complexity of solving such a one-dimensional array problem is O (nlogn).

At the same time, applying one-dimensional thinking to this problem (two-dimensional), the complexity is either O (m ^ 2 * nlogn) or O (n ^ 2 * mlogm);

** The key point is how to relate to the “one-dimensional” problem: obviously “the sum of the target submatrix” is equal to “the sum of the submatrix formed by the right column of the submatrix and the left column of the original matrix” - “the left column of the submatrix and the left column of the original matrix, forming the sum of the submatrix” **

We can use area [r] to represent “the right column of the submatrix and the left column of the original matrix, forming the sum of the submatrix”, and use area [l - 1] to represent “the left column of the submatrix and the left column of the original matrix, forming the sum of the submatrix”, then:
target=area[r]−area[l−1]⩽k

This is exactly the same as our “one-dimensional problem”. At the same time, the size of area [r] can be directly determined from the “up and down row” & “right column”, and the “ordered set” stores all the areas [r] in the process of r. In order to achieve “binary” search for the smallest area [l - 1] that meets the area [r] − karea [l − 1] condition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
var maxSumSubmatrix = function(matrix, k) {
  let ans = Number.MIN_SAFE_INTEGER;
  const m = matrix.length;
  const n = matrix[0].length;
  const sum = new Array(m + 1).fill(0).map(() => {
    return new Array(n + 1).fill(0)
  });
  //Initialize the prefix and array, sum [i] [j] represents the sum of all cells from (0,0) to (i - 1, j - 1)
  for(let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
    }
  }
  //traverse the upper boundary of the submatrix
  for(let top = 1; top <= m; top++) {
    //traverse the lower boundary of the submatrix
    for(let bot = top; bot <= m; bot++) {
      //At this point, we can start transforming the two-dimensional matrix problem into a one-dimensional matrix problem
      //Because the problem of upper and lower boundaries has already been solved in the double-layer loop

      //Use ordered collections to maintain all traversed right boundaries
      //That is, the sum between the upper and lower boundaries, from column 0 to the right boundary
      const sumSet = new TreeSet();
      sumSet.add(0);

      for(let r = 1; r <= n; r++) {
        //The sum of all cells from column 0 to column r, from row top to row bot.
        const right = sum[bot][r] - sum[top - 1][r];
        //Find a minimum value greater than or equal to right - k by dichotomy
        const left = sumSet.ceiling(right - k);
        if (left ! null) {
          ans = Math.max(ans, right - left);
        }
        //Add the traversed right to the ordered set for the next loop
        //here is a point, the right must be increasing because there is no negative value in the cell
        sumSet.add(right);
      }
    }
  }
  return ans;
};

Space optimization

It is not difficult to find that the process of searching the target submatrix in the original matrix is strictly “top to bottom” & “left to right”.

Therefore, we can delegate the logic of calculating the sum of prefixes to the loop of searching for submatrices, thereby reducing the space complexity of O (m ∗ n) to O (n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var maxSumSubmatrix = function(matrix, k) {
  let ans = Number.MIN_SAFE_INTEGER;
  const m = matrix.length;
  const n = matrix[0].length;
  For (let i = 0; i < m; i ++) { // i is the starting point of the row number
    const sum = new Array(n).fill(0);
    For (let j = i; j < m; j ++) { // j is the end of the line number
      for(let c = 0; c < n; c++) {
        Sum [c] += matrix [j] [c];//sum [c] refers to the sum of all the data in column c between row i and row j
      }
      const sumSet = new TreeSet();
      sumSet.add(0);
      let s = 0;
      for(const v of sum) {
        s += v;
        const ceil = sumSet.ceiling(s - k); 
        if (ceil != null) {
          ans = Math.max(ans, s - ceil);
        }
        sumSet.add(v);
      }
    }
  }
  return ans;
};

Ordered set TreeSet

In fact, due to the special reasons of this question, each add is incremental and does not require additional sorting, so add can be pushed directly in the array.

And binary search can see my other blog: https://sunra.top/posts/e421a043/

Reference link:

https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k/solution/gong-shui-san-xie-you-hua-mei-ju-de-ji-b-dh8s/

https://leetcode-cn.com/u/ac_oier/