Count Submatrices With All Ones

medium monotonic stack histogram matrix

Problem

Given an m × n binary matrix mat, return the number of submatrices that contain only ones. A submatrix is any contiguous rectangular block of cells, counted once per distinct top-left/bottom-right corner pair.

Inputmat = [[1,0,1],[1,1,0],[1,1,0]]

Output13

6 of size 1×1, 2 of size 1×2, 3 of size 2×1, 1 of size 2×2, 1 of size 3×1 → 13.

Inputmat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]

Output24

8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 all-ones rectangles.

mat (rows separated by ; , values by ,)

def numSubmat(mat):
    m, n = len(mat), len(mat[0])
    heights = [0] * n
    total = 0
    for r in range(m):
        for j in range(n):
            heights[j] = heights[j] + 1 if mat[r][j] else 0
        st, summ = [], [0] * n
        for j in range(n):
            while st and heights[st[-1]] >= heights[j]:
                st.pop()
            k = st[-1] if st else -1
            summ[j] = (summ[k] if st else 0) + heights[j] * (j - k)
            st.append(j)
            total += summ[j]
    return total

function numSubmat(mat) {
  const m = mat.length, n = mat[0].length;
  const heights = new Array(n).fill(0);
  let total = 0;
  for (let r = 0; r < m; r++) {
    for (let j = 0; j < n; j++)
      heights[j] = mat[r][j] ? heights[j] + 1 : 0;
    const st = [], summ = new Array(n).fill(0);
    for (let j = 0; j < n; j++) {
      while (st.length && heights[st[st.length - 1]] >= heights[j]) st.pop();
      const k = st.length ? st[st.length - 1] : -1;
      summ[j] = (st.length ? summ[k] : 0) + heights[j] * (j - k);
      st.push(j);
      total += summ[j];
    }
  }
  return total;
}

int numSubmat(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] heights = new int[n];
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int j = 0; j < n; j++)
            heights[j] = mat[r][j] == 1 ? heights[j] + 1 : 0;
        Deque<Integer> st = new ArrayDeque<>();
        int[] summ = new int[n];
        for (int j = 0; j < n; j++) {
            while (!st.isEmpty() && heights[st.peek()] >= heights[j]) st.pop();
            int k = st.isEmpty() ? -1 : st.peek();
            summ[j] = (st.isEmpty() ? 0 : summ[k]) + heights[j] * (j - k);
            st.push(j);
            total += summ[j];
        }
    }
    return total;
}

int numSubmat(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> heights(n, 0);
    int total = 0;
    for (int r = 0; r < m; r++) {
        for (int j = 0; j < n; j++)
            heights[j] = mat[r][j] ? heights[j] + 1 : 0;
        vector<int> st, summ(n, 0);
        for (int j = 0; j < n; j++) {
            while (!st.empty() && heights[st.back()] >= heights[j]) st.pop_back();
            int k = st.empty() ? -1 : st.back();
            summ[j] = (st.empty() ? 0 : summ[k]) + heights[j] * (j - k);
            st.push_back(j);
            total += summ[j];
        }
    }
    return total;
}

Explanation

Every all-ones submatrix has a bottom edge sitting on some row. So we fix each row in turn as the bottom edge and count all all-ones rectangles whose bottom lies on it; summing over the rows gives the answer with no double counting.

To do that we keep a heights array, where heights[j] is the number of consecutive 1s ending at the current row in column j (a 0 resets it). This turns the current row into a histogram: a column of height h means a 1×h vertical strip of ones rising from the current row.

For a fixed bottom row we want, for each right edge j, the number of all-ones rectangles ending exactly at column j. Let summ[j] be that count. We sweep left to right with a monotonic increasing stack of column indices.

Before placing j we pop every column whose height is ≥ heights[j]; those taller columns can't extend a rectangle of height heights[j] rightward past j. If a shorter column k remains on top, then summ[j] = summ[k] + heights[j] · (j − k): the rectangles from k carry over, plus heights[j] new rectangles for each of the j − k columns the current height spans. If the stack is empty, the current height spans all columns 0..j, so summ[j] = heights[j] · (j + 1).

Adding every summ[j] into total accumulates the count. Each column is pushed and popped at most once per row, so the whole thing runs in O(m·n) time and O(n) space.

Example: [[1,0,1],[1,1,0],[1,1,0]]. Row heights become [1,0,1], then [2,1,0], then [3,2,0]; summing the per-row counts gives 3 + 4 + 6 = 13.

Time: O(m·n) Space: O(n)