1504. Count Submatrices With All Ones

Description

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

 

Example 1:

Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation: 
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2. 
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.

Example 2:

Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
Output: 24
Explanation: 
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3. 
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2. 
There are 2 rectangles of side 3x1. 
There is 1 rectangle of side 3x2. 
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

 

Constraints:

• 1 <= m, n <= 150
• mat[i][j] is either 0 or 1.

 

Solutions

Solution: Dynamic Programming

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

 

JavaScript

/**
 * @param {number[][]} mat
 * @return {number}
 */
const numSubmat = function (mat) {
  const m = mat.length;
  const n = mat[0].length;
  const dp = new Array(m + 1)
    .fill('')
    .map(_ => new Array(n + 1).fill(0));
  let result = 0;

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

      dp[row][col] = value ? dp[row][col - 1] + value : 0;
    }
  }

  for (let row = 1; row <= m; row++) {
    for (let col = 1; col <= n; col++) {
      if (!dp[row][col]) continue;
      let minW = dp[row][col];

      for (let k = row; k >= 0; k--) {
        if (!dp[k][col]) break;
        minW = Math.min(minW, dp[k][col]);
        result += minW;
      }
    }
  }
  return result;
};