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

numSubmat.js

/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSubmat = function(mat) {
  const rows = mat.length;
  const cols = mat[0].length;
  let total = 0;

  // Step 1: Preprocess each row to build horizontal histograms
  // Each cell mat[i][j] will store the number of consecutive 1s to the left (including itself)
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (mat[i][j] === 1 && j > 0) {
        mat[i][j] += mat[i][j - 1]; // Add count from the left
      }
      // If mat[i][j] is 0, it stays 0 (no consecutive 1s)
    }
  }

  // Step 2: Count submatrices ending at each cell (i, j)
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      let minWidth = Infinity;

      // Look upward from row i to 0
      for (let k = i; k >= 0 && mat[k][j] > 0; k--) {
        // Update the minimum width of 1s in this vertical stack
        minWidth = Math.min(minWidth, mat[k][j]);

        // Add the number of submatrices ending at (i, j) with height (i - k + 1)
        total += minWidth;
      }
    }
  }

  return total;
};