363. Max Sum of Rectangle No Larger Than K

Description

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
• -105 <= k <= 105

 

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

 

Solutions

Solution: Prefix Sum

• Time complexity: O(m²n²)
• Space complexity: O(m)

 

JavaScript

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
const maxSumSubmatrix = function (matrix, k) {
  const m = matrix.length;
  const n = matrix[0].length;
  let result = Number.MIN_SAFE_INTEGER;

  for (let upperRow = 0; upperRow < m; upperRow++) {
    const prefixCol = new Array(n).fill(0);

    for (let row = upperRow; row < m; row++) {
      let sum = 0;
      let maxSubSum = Number.MIN_SAFE_INTEGER;

      for (let col = 0; col < n; col++) {
        prefixCol[col] += matrix[row][col];
        sum = Math.max(prefixCol[col], sum + prefixCol[col]);
        maxSubSum = Math.max(sum, maxSubSum);
      }
      if (maxSubSum === k) return maxSubSum;
      if (maxSubSum < k) {
        result = Math.max(maxSubSum, result);
        continue;
      }
      maxSubSum = Number.MIN_SAFE_INTEGER;

      for (let leftCol = 0; leftCol < n; leftCol++) {
        let sum = 0;

        for (let col = leftCol; col < n; col++) {
          sum += prefixCol[col];
          if (sum > k) continue;
          maxSubSum = Math.max(sum, maxSubSum);
        }
        result = Math.max(maxSubSum, result);
      }
      if (result === k) return result;
    }
  }
  return result;
};