This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 363 on LeetCode. The rectangular area does not exceed the maximum value sum of K, and difficulty is difficult.

Tag: “dichotomy”, “prefix and”

Given a matrix matrix of m x n and an integer k, find and return the largest sum of values up to k in the rectangular region inside the matrix.

The problem data guarantees that there will always be a rectangular region of values and values not exceeding K.

 

Example 1:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2 Output: 2 Explanation: the sum of the values of the rectangle [[0, 1],[-2,3] circled by the blue border is 2, and 2 is the largest number not exceeding k (k = 2).Copy the code

Example 2:

Input: matrix = [[2,2,-1]], k = 3Copy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -100 <= matrix[i][j] <= 100
  • –
    1 0 5 10^5     <= k <=
    1 0 5 10^5

Naive two-dimensional prefix sum

304. The sum of two dimensional prefixes is the same as the sum of two dimensional prefixes. Two dimensional region and retrieval – matrix immutable. In this case, the complexity of preprocessing prefixes is O(m∗n)O(m * n)O(m∗n).

Searching for all submatrices requires enumerating “upper left corner of the rectangle” and “lower right corner of the rectangle” with the complexity O(m2∗n2)O(m^2 * n^2)O(m2∗n2).

Therefore, the overall complexity is O(m2∗n2)O(m^2 * n^2)O(m2∗n2) if the problem is used as a two-dimensional prefix and template problem.

The range is 10210^2102, and the computation is 10810^8108, which theoretically times out, but when we enumerate the “upper left corner of the rectangle” (I,j)(I,j)(I,j), We only need to search the point (p,q)(p,q)(p,q) located at the lower right of (I,j)(I,j)(I,j) as “the lower right corner of the rectangle”, so in fact, we cannot take m2∗n2m^2 * n^2m2∗n2, But there is still a timeout risk (2021/04/20 Java tests pass, C++ will TLE using vector).

Code:

class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1]; }}int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                for (int p = i; p <= m; p++) {
                    for (int q = j; q <= n; q++) {
                        int cur = sum[p][q] - sum[i - 1][q] - sum[p][j - 1] + sum[i - 1][j - 1];
                        if (cur <= k) {
                            ans = Math.max(ans, cur);
                        } 
                    }
                }
            }
        }
        returnans; }}Copy the code
  • Time complexity: The complexity of preprocessing prefixes and arrays is O(m∗n)O(M * n)O(m∗n) O(m∗n), and the complexity of finding answers is O(m2∗n2)O(M ^2 * n^2)O(m2∗n2). The overall complexity is O(m2∗n2)O(m^2 * n^2)O(m2∗n2).
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

Prefix and & dichotomy (abstract one dimension)

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

In other words, by enumeration
( i . j ) (i,j) 和
( p . q ) (p,q) To uniquely determine the four edges of the submatrix, each coordinate point can be considered as an edge of the submatrix.

Now that we have four edges to determine, how can we reduce complexity?

For simplicity, let’s first consider the sum of two numbers, also enumerated.

You can enumerate two numbers violently in the sum of 1. Or you can enumerate just one number and use data structures (hash tables) to speed up the search for the other number (this is a general “reduce enumeration complexity” way of thinking).

Accordingly, we can enumerate three of the edges and then use data structures to speed up finding the fourth edge.

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

The problem then becomes “how to quickly find the position of the fourth edge (yellow)”.

We can further reduce the problem to consider the case where the matrix has only one row (one dimension) :

At this point, the problem is further transformed into “in a one-dimensional array, solve the sum of the largest continuous subarray not exceeding K”.

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

Assuming that we have obtained the prefix and sum of the one-dimensional array, we can obtain the sum of the subscript range [I,j][I,j][I,j] :


a r e a S u m ( i . j ) = s u m [ j ] – s u m [ i – 1 ] ⩽ k areaSum(i, j) = sum[j] – sum[i – 1] \leqslant k

After deformation:


s u m [ j ] ⩽ k + s u m [ i – 1 ] sum[j] \leqslant k + sum[i – 1]

We have two ways of maximizing areaSum(I,j)areaSum(I,j) :

  • Determines (enumeration) the left endpoint positioni, the maximum right endpoint that meets the condition is obtainedsum[j]
  • Determines (enumeration) the right endpoint positionj, the minimum left endpoint that meets the condition is obtainedsum[i]

For a one-dimensional array with no negative weights, we can enumerate the left endpointsiAt the same time, using the “monotone increasing” property of prefix and, find the match through “dichotomy”
s u m [ j ] ⩽ k + s u m [ i – 1 ] sum[j] \leqslant k + sum[i – 1] Maximum value of conditionsum[j]To solve the problem.

But with negative weights, prefixes and sums lose their monotonically increasing properties and we cannot use enumerationsiAnd combined with “binary” searchjIn the practice.

At this point, the process needs to be reversed: we enumerate from left to rightjAnd use the “ordered collection” structure to maintain the traversed location to find a match
s u m [ j ] – k ⩽ s u m [ i ] sum[j] – k \leqslant sum[i] The minimum value of the conditionsum[i]To solve the problem.

Based on the above analysis, solving such a one-dimensional array problem is O(nlog⁡n)O(n\log{n})O(nlogn).

Applying this idea to two dimensions requires a little bit of abstraction.

Meanwhile, applying the one-dimensional approach to the problem (two dimensions), the complexity is either O(m2∗nlog⁡n)O(m^2 * n\log{n})O(m2∗nlogn) or O(n2∗mlog⁡m)O(n^2 * m\log{m})O(n2∗mlogm).

Let’s ignore the “maximization of binary returns” problem and assume that we are fixed enumerating “upstream and downstream” and “right column”, then the only way to determine a submatrix depends on the “left column” :

The emphasis is on 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 sum of the submatrix formed by the left column of the submatrix and the left column of the original matrix”

We can use area[r] to represent the sum of the submatrices formed by the right column of the submatrix and the left column of the original matrix. We can use area[L – 1] to represent the sum of the submatrices formed by the left column of the submatrix and the left column of the original matrix.


t a r g e t = a r e a [ r ] – a r e a [ l – 1 ] ⩽ k target = area[r] – area[l – 1] \leqslant k

This is exactly the same as our “one-dimensional problem”, and we can directly determine the size of area[r] by “up and down” & “right column”. Area [r] ⩽area[L −1]area[r] -k \leqslant area[L-1]area[R]−k⩽area[L −1] The minimum area of the condition [L-1].

So far, we completely transform the problem into a “one-dimensional problem” by preprocessing prefix and + exclusion principle.

Code:

class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;

        // Preprocess the prefix and
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1]; }}int ans = Integer.MIN_VALUE;
        // iterate over the upper boundary of the submatrix
        for (int top = 1; top <= m; top++) {
            // Iterate over the lower boundary of the submatrix
            for (int bot = top; bot <= m; bot++) {
                // Use "ordered set" to maintain all traversal to the right boundary
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                // Iterate over the right boundary of the submatrix
                for (int r = 1; r <= n; r++) {
                    // Calculate right by prefix
                    int right = sum[bot][r] - sum[top - 1][r];
                    // find left by dichotomy
                    Integer left = ts.ceiling(right - k);
                    if(left ! =null) {
                        int cur = right - left;
                        ans = Math.max(ans, cur);
                    }
                    // Add the traversed right to the ordered setts.add(right); }}}returnans; }}Copy the code
  • Time complexity: the upper and lower boundary complexity of enumeration is
    O ( m 2 ) O(m^2)     ; The enumeration right boundary is
    O ( n ) O(n)     , the use ofTreeSet(based on red-black tree) the left boundary complexity of storage and lookup is
    O ( log ⁡ n ) O(\log{n})     . The overall complexity is
    O ( m 2 ∗ n log ⁡ n ) O(m^2 * n\log{n})
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

Maximize binary benefits

In the above solution, we enumerate the “upstream and downstream” and “right column” first, and then “dichotomize” the “left column” by TreeSet.

In fact, we need to apply the binary process to large rows or columns to maximize the efficiency of our lookups (and answer the advanced part of the question).

Code:

class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        int[][] sum = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1]; }}// Set the right boundary
        boolean isRight = n > m;
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= (isRight ? m : n); i++) {
            for (int j = i; j <= (isRight ? m : n); j++) {
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                for (int fixed = 1; fixed <= (isRight ? n : m); fixed++) {
                    int a = isRight ? sum[j][fixed] - sum[i - 1][fixed] : sum[fixed][j] - sum[fixed][i - 1];
                    Integer b = ts.ceiling(a - k);
                    if(b ! =null) {
                        intcur = a - b; ans = Math.max(ans, cur); } ts.add(a); }}}returnans; }}Copy the code
  • Time complexity: preprocessing the prefix sum of “per line” or “per column”, and the complexity is O(m∗n)O(M * n)O(m∗n); Enumerate the “upstream and downstream” or “left and right” of the submatrix, the complexity is O(min⁡(m,n)2)O(\min(m, n)^2)O(min(m,n)2); Combining a two-dimensional prefix and applying a one-dimensional maximum continuous subarray solution, the complexity is Max ⁡(m,n)log⁡ Max ⁡(m,n)\ Max (m,n)\ log{\ Max (m,n)} Max (m,n)logmax(m,n). The overall complexity of O (min ⁡ (m, n) 2 ∗ Max ⁡ (m, n) log ⁡ Max ⁡ (m, n)) O (\ min (m, n) ^ 2 *, Max (m, n), log {\ Max (m, n)}) O (min (m, n) 2 ∗ Max (m, n) logmax (m, n))
  • Space complexity: O(m∗n)O(M * n)O(m∗n)

Space optimization

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

Therefore, we can reduce the logic of calculating prefix sums to the loop of searching submatrices, thus reducing the spatial complexity of O(m∗n)O(m * n)O(m∗n) O(m∗n)O(m * n)O(m∗n) to O(Max ⁡(m,n))O(\ Max (m,n))O(Max (m,n)).

Code:

class Solution {
    public int maxSumSubmatrix(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;
        boolean isRight = n > m;
        int[] sum = isRight ? new int[n + 1] : new int[m + 1];
        int ans = Integer.MIN_VALUE;
        for (int i = 1; i <= (isRight ? m : n); i++) {
            Arrays.fill(sum, 0);
            for (int j = i; j <= (isRight ? m : n); j++) {
                TreeSet<Integer> ts = new TreeSet<>();
                ts.add(0);
                int a = 0;
                for (int fixed = 1; fixed <= (isRight ? n : m); fixed++) {
                    sum[fixed] += isRight ? mat[j - 1][fixed - 1] : mat[fixed - 1][j - 1]; a += sum[fixed]; Integer b = ts.ceiling(a - k);if(b ! =null) {
                        intcur = a - b; ans = Math.max(ans, cur); } ts.add(a); }}}returnans; }}Copy the code
  • Time complexity: preprocessing the prefix sum of “per line” or “per column”, and the complexity is O(m∗n)O(M * n)O(m∗n); Enumerate the “upstream and downstream” or “left and right” of the submatrix, the complexity is O(min⁡(m,n)2)O(\min(m, n)^2)O(min(m,n)2); Combining a two-dimensional prefix and applying a one-dimensional maximum continuous subarray solution, the complexity is Max ⁡(m,n)log⁡ Max (m,n)\ Max (m,n)\ log{Max (m,n)} Max (m,n)logmax(m,n). The overall complexity of O (min ⁡ (m, n) 2 ∗ Max ⁡ (m, n) log ⁡ Max ⁡ (m, n)) O (\ min (m, n) ^ 2 *, Max (m, n), log {\ Max (m, n)}) O (min (m, n) 2 ∗ Max (m, n) logmax (m, n))
  • Space complexity: O(Max ⁡(m,n))O(\ Max (m,n))O(Max (m,n))

The last

This difficult problem is still a little difficult, digging friends learned 🤣

It is suggested to focus on how the “abstract one dimension” is derived