Given a binary matrix, find the number of sub-matrices with all ones

Given a matrix A, let Aij denote the element of the i'th row and j'th column. $$A_{i,j}\in \{0, 1\}$$

Find the number of sub-matrices with all ones.

1 <= #rows, #columns <= 150

P.S. This apparently can be solved in O(#rows x #columns) using dynamic programming and stack. I just can't wrap my head around how this can be achieved.

• What do you call a sub-matrix? Feb 20, 2023 at 19:55

Here is a solution in $$O(n\cdot m)$$, where $$n, m$$ are the number of rows and columns respectively.

Let us iterate over all columns of the matrix from left to right. For each column let us iterate over all cells in this column and for each cell $$A[i,j]$$ let us compute the number of submatrices of ones, having $$A[i,j]$$ as the bottom-right corner. Let $$\mathcal{T}[i,j]$$ be the set of all these submatrices, and $$T[i,j] = |\mathcal{T}[i,j]|$$ be the value we want to compute.

Let $$Z[i,j]$$ be the longest number of ones on the $$i$$th row ending at the $$j$$th column. Then it holds $$Z[i,j] = \begin{cases} 0 &\colon A[i,j] = 0\\ A[i][j-1]+1 &\colon \text{otherwise} \end{cases}$$ Hense, we can compute this value in constant time for each cell.

Now for a cell $$A[i,j]$$ assume that $$Z[i-1,j] = k$$, then all matrices in $$\mathcal{T}[i][j]$$ can that span at least two rows can have at most $$k$$ columns, independent of $$Z[r, j]$$ for $$r < i-1$$. This monotonousity allows us to forget'' the values of $$Z[r, j]$$ where $$r adn $$Z[r,j]>Z[i-1, j]$$.

Therefore, we define a stack $$\mathcal{S}_j$$ for each column. We start with empty column, and when iterating over the cells of the column we update the stack as follows:

If $$A[i][j] = 0$$, then empty the stack and set $$T[i][j] = 0$$, otherwise do the following

while not stack.empty
let r = stack.top
if z[r,j] >= z[i,j]
stack.pop
else
break
// now r is the last row having Z[r][j] < Z[i][j]
if not stack.empty
T[i,j] = T[r,j]
T[i,j] += Z[i][j] * (i-r)
stack.push(i)


So the stack keeps sequence of rows of increasing Z[i,j]. The whole dynamic programming is in the line T[i,j] = T[r,j], since we can extend each submatrix ending at $$A[r,j]$$ to one ending at $$A[i,j]$$ (since all the lines $$i'$$ between $$r$$ and $$i$$ have a greater value of $$Z[i',j]$$ than $$Z[r, j]$$. We als have all submatrices using rows $$r+1$$ to $$i$$ and the last $$Z[i,j]$$ columns.

Note that we push each cell exactly once to the stack, and hence can pop it at most once, since all other operations are done in constant time per cell, we achieve a total running time of $$O(n\cdot m)$$.