Leetcode 363: Max Sum of Rectangle No Larger Than K

Given an m x n matrix matrix and an integer k, return the max sum of a rectangle in the matrix such that its sum is no larger than k.

It is guaranteed that there will be a rectangle with a sum no larger than k.

Example 1:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

Example 2:

Input: matrix = [[2,2,-1]], k = 3
Output: 3

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 3000
• 1 <= m * n <= 5 * 104
• -100 <= matrix[i][j] <= 100
• -105 <= k <= 105

Follow up: What if the number of rows is much larger than the number of columns?

Problem Analysis:

A simple method is computing all submatrices and find the answer, and we can use dynamic programming to optimize the computing procedure

Solution 1:

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
        int rows = matrix.size();
        int columns = matrix[0].size();
        int res = numeric_limits<int>::min();
        
        vector<vector<vector<vector<int>>>> data(rows, vector<vector<vector<int>>>(columns, vector<vector<int>>(rows, vector<int>(columns, 0))));
        for (int rlen = 0; rlen < rows; ++ rlen) {
            for (int clen = 0; clen < columns; ++clen) {
                for (int i = 0; i + rlen < rows; ++i) {
                    for (int j = 0; j + clen < columns; ++j) {
                        if (rlen == 0 && clen == 0) {
                            data[i][j][i + rlen][j + clen] = matrix[i][j];
                        } else if (rlen == 0) {
                            data[i][j][i + rlen][j + clen] = data[i][j][i + rlen][j + clen - 1] + matrix[i + rlen][j + clen];
                        } else if (clen == 0) {
                            data[i][j][i + rlen][j + clen] = data[i][j][i + rlen - 1][j + clen] + matrix[i + rlen][j + clen];                          
                        } else {
                            data[i][j][i + rlen][j + clen] = data[i][j][i + rlen - 1][j + clen] + data[i][j][i + rlen][j + clen - 1] - data[i][j][i + rlen - 1][j + clen - 1] + matrix[i + rlen][j + clen];                        
                        }
                        if (data[i][j][i + rlen][j + clen] == k) return k;
                        else if (data[i][j][i + rlen][j + clen] < k)
                            res = max(res, data[i][j][i + rlen][j + clen]);
                    }
                }
            }
        }
        
        return res;
    }
};

But this solution will cause error of time limit exceeded. So we will continue to optimize it.

We can scan the matrix in rows from up to down, compute sums from column 0 to column 1,2,…,n. Then subsum[i][j] from the rows, where i, j is column index, j > i, is sum[j]-sum[i]

Solution 2:

class Solution {
public:
  int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
    int result = std::numeric_limits<int>::min();
    int rows = matrix.size();
    if (rows == 0) return result;
    int cols = matrix[0].size();
    if (cols == 0) return result;
    for (int i = 0; i < cols; ++i) {
      vector<long long> sum(rows, 0);
      for (int j = i; j < cols; ++j) {
        for (int l = 0; l < rows; ++l) {
          sum[l] += matrix[l][j];
        }
  
        int current = 0;
        int current_max = std::numeric_limits<int>::min();
        set<int> values;
        values.insert(0);
        for (auto item: sum) {
          current += item;
          auto it = values.lower_bound(current - k);
          if (it != values.end()) current_max = max(current_max, current - *it);
          values.insert(current);
        }
        result = max(result, current_max);
      }
    }
    return result;
  }
};

The second solution’s space complexity are O(n), time complexity is O(mn²lgm)