1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Description

Given a m x n matrix mat and an integer threshold, return the maximum side-length of a square with a sum less than or equal to threshold or return 0 if there is no such square.

 

Example 1:

Input: mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4
Output: 2
Explanation: The maximum side length of square with sum less than 4 is 2 as shown.

Example 2:

Input: mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1
Output: 0

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 300
• 0 <= mat[i][j] <= 104
• 0 <= threshold <= 105

 

Solutions

Solution: Binary Search + Prefix Sum

• Time complexity: O(mnlog*Min(m,n))
• Space complexity: O(mn)

 

JavaScript

/**
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
const maxSideLength = function (mat, threshold) {
  const m = mat.length;
  const n = mat[0].length;
  const prefixSum = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  let left = 0;
  let right = Math.min(m, n);
  let result = 0;

  for (let row = 1; row <= m; row++) {
    for (let col = 1; col <= n; col++) {
      const value = mat[row - 1][col - 1];
      const preRowSum = prefixSum[row - 1][col];
      const preColSum = prefixSum[row][col - 1];
      const cornerSum = prefixSum[row - 1][col - 1];

      prefixSum[row][col] = preRowSum + preColSum + value - cornerSum;
    }
  }

  const isValidSideLength = len => {
    if (!len) return true;

    for (let row = len; row <= m; row++) {
      for (let col = len; col <= n; col++) {
        const preRowSum = prefixSum[row - len][col];
        const preColSum = prefixSum[row][col - len];
        const cornerSum = prefixSum[row - len][col - len];
        const sum = prefixSum[row][col] - preRowSum - preColSum + cornerSum;

        if (sum <= threshold) return true;
      }
    }

    return false;
  };

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (isValidSideLength(mid)) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
};