Question

Formatted question description: https://leetcode.ca/all/363.html

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 <= 100
-100 <= matrix[i][j] <= 100
-10⁵ <= k <= 10⁵

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

Algorithm

To establish a cumulative sum, refer to the previous question Range Sum Query 2D-Immutable, which can quickly find any interval sum.

When traversing to (i, j), calculate sum(i, j), which represents the sum of the rectangle (0, 0) to (i, j), and then traverse all the sub-rectangles in this rectangle, and calculate the sum and phase K Compared with this, it can traverse all the sub-rectangles of the original rectangle.

Code

import java.util.TreeSet;

public class Max_Sum_of_Rectangle_No_Larger_Than_K {


    class Solution {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }

            int m = matrix.length,
                n = matrix[0].length,
                res = Integer.MIN_VALUE;
            int[][] sum = new int[m][n]; // sum of the rectangle (0, 0) to (i, j)
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int area = matrix[i][j];
                    if (i > 0) area += sum[i - 1][j];
                    if (j > 0) area += sum[i][j - 1];
                    if (i > 0 && j > 0) area -= sum[i - 1][j - 1];
                    sum[i][j] = area;

                    for (int r = 0; r <= i; ++r) {
                        for (int c = 0; c <= j; ++c) {
                            int d = sum[i][j];
                            if (r > 0) d -= sum[r - 1][j];
                            if (c > 0) d -= sum[i][c - 1];
                            if (r > 0 && c > 0) d += sum[r - 1][c - 1];
                            if (d <= k) res = Math.max(res, d);
                        }
                    }
                }
            }
            return res;
        }
    }

    class Solution2 {
        public int maxSumSubmatrix(int[][] matrix, int k) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }

            int m = matrix.length;
            int n = matrix[0].length;

            int[][] preSum = new int[m][n + 1];

            for (int i = 0; i < m; i++) {
                for (int j = 1; j <= n; j++) {
                    preSum[i][j] = preSum[i][j - 1] + matrix[i][j - 1];
                }
            }

            int ans = Integer.MIN_VALUE;
            for (int c1 = 1; c1 <= n; c1++) {
                for (int c2 = c1; c2 <= n; c2++) {
                    int[] preSumRow = new int[m];
                    for (int row = 0; row < m; row++) {
                        preSumRow[row] = preSum[row][c2] - preSum[row][c1 - 1];
                    }

                    ans = Math.max(ans, getMaxSubarrayHelper(preSumRow, k));
                }
            }

            return ans;
        }

        private int getMaxSubarrayHelper(int[] nums, int target) {
            TreeSet<Integer> treeSet = new TreeSet<>();

            int ans = Integer.MIN_VALUE;
            int[] preSum = new int[nums.length + 1];

            for (int i = 1; i <= nums.length; i++) {
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }

            treeSet.add(0);
            for (int i = 1; i <= nums.length; i++) {
                Integer num = preSum[i] - target;
                Integer ceiling = treeSet.ceiling(num);

                if (ceiling != null) {
                    ans = Math.max(ans, preSum[i] - ceiling);
                }

                treeSet.add(preSum[i]);
            }

            return ans;
        }
    }
}

// OJ: https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
// Time: O(M^2 * NlogN)
// Space: O(N)
class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& A, int k) {
        int M = A.size(), N = A[0].size(), ans = INT_MIN;
        for (int i = 0; i < M; ++i) { // starting row
            vector<int> prefix(N, 0);
            for (int j = i; j < M; ++j) { // ending row
                int sum = 0;
                set<int> s{0};
                for (int t = 0; t < N; ++t) {
                    sum += A[j][t];
                    prefix[t] += sum;
                    int target = prefix[t + 1] - k;
                    auto it = s.lower_bound(target);
                    if (it != s.end()) {
                        ans = max(ans, prefix[t] - *it);
                    }
                    s.insert(prefix[t]);
                }
            }
        }
        return ans;
    }
};

import bisect


class Solution(object):
  def maxSumSubmatrix(self, matrix, k):
    """
    :type matrix: List[List[int]]
    :type k: int
    :rtype: int
    """
    ans = float("-inf")
    dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
    for i in range(0, len(matrix)):
      for j in range(0, len(matrix[0])):
        dp[i][j] = dp[i][j - 1] + matrix[i][j]
    for start in range(0, len(matrix[0])):
      for end in range(start, len(matrix[0])):
        sums = [0]
        subsum = 0
        for i in range(0, len(matrix)):
          if start > 0:
            subsum += dp[i][end] - dp[i][start - 1]
          else:
            subsum += dp[i][end]
          idx = bisect.bisect_left(sums, subsum - k)
          if idx < len(sums):
            ans = max(ans, subsum - sums[idx])
          bisect.insort(sums, subsum)
    return ans

363 - Max Sum of Rectangle No Larger Than K

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions