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

Example 3:

Input: mat = [[1,1,1,1],[1,0,0,0],[1,0,0,0],[1,0,0,0]], threshold = 6
Output: 3

Example 4:

Input: mat = [[18,70],[61,1],[25,85],[14,40],[11,96],[97,96],[63,45]], threshold = 40184
Output: 2

 

Constraints:

• 1 <= m, n <= 300
• m == mat.length
• n == mat[i].length
• 0 <= mat[i][j] <= 10000
• 0 <= threshold <= 10^5

Solution(javascript)

/** 自底向上的 DP, O(n^2), 对比 221，思路不对
 * @param {number[][]} mat
 * @param {number} threshold
 * @return {number}
 */
// const maxSideLength = function (mat = [], threshold) {
//   const dp = new Array(mat.length).fill(0).map(() => new Array(mat[0].length))
//   let max = 0
//   for (let i = 0; i < mat.length; i++) {
//     for (let j = 0; j < mat[i].length; j++) {
//       if (dp[i - 1] && dp[i - 1][j - 1]) {
//         const [prevSum, prevLength] = dp[i - 1][j - 1]
//         let currentSum = prevSum + mat[i][j]
//         for (let row = i - prevLength; row <= i - 1; row++) {
//           currentSum += mat[row][j]
//         }
//         for (let column = j - prevLength; column <= j - 1; column++) {
//           currentSum += mat[i][column]
//         }
//         if (currentSum <= threshold) { // 这里有点问题，不满足的情况我们就直接跳转到下一步了
//           dp[i][j] = [currentSum, prevLength + 1]
//           max = Math.max(max, dp[i][j][1])
//           continue
//         }
//       }
//       dp[i][j] = mat[i][j] <= threshold ? [mat[i][j], 1] : [0, 0]
//       max = Math.max(max, dp[i][j][1])
//     }
//   }
//   return max
// }

// O(m*n * min(m,n))
const maxSideLength = function (mat = [], threshold) {
  let max = 0
  const aux = (rowIndex, columnIndex, currentLength, currentSum) => {
    if (
      rowIndex + currentLength >= mat.length
      || columnIndex + currentLength >= mat.length
    ) {
      return currentLength
    }
    let nextSum = currentSum + mat[rowIndex + currentLength][columnIndex + currentLength]
    for (let row = rowIndex; row < rowIndex + currentLength; row++) {
      nextSum += mat[row][columnIndex + currentLength]
    }
    for (let column = columnIndex; column < columnIndex + currentLength; column++) {
      nextSum += mat[rowIndex + currentLength][column]
    }
    if (nextSum <= threshold) {
      return aux(rowIndex, columnIndex, currentLength + 1, nextSum)
    }
    return currentLength
  }
  for (let i = 0; i < mat.length; i++) {
    for (let j = 0; j < mat[i].length; j++) {
      max = Math.max(aux(i, j, 0, 0), max)
    }
  }
  return max
}