1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ What do you call a sub-matrix? $\endgroup$
    – Dmitry
    Feb 20, 2023 at 19:55

1 Answer 1

1
$\begingroup$

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<j$ 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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.