Table of Contents

You are given a matrix with `n`

rows and `m`

columns. Find the largest submatrix consisting of only zeros (a submatrix is a rectangular area of the matrix).

## 1. Algorithm

Elements of the matrix will be `a[i][j]`

, where `i = 0...n - 1`

, `j = 0... m - 1`

. For simplicity, we will consider all non-zero elements equal to 1.

### 1.1. Step 1: Auxiliary dynamic

First, we calculate the following auxiliary matrix: `d[i][j]`

, nearest row that has a 1 above `a[i][j]`

. Formally speaking, `d[i][j]`

is the largest row number (from `0`

to `i - 1`

), in which there is a element equal to `1`

in the `j`

-th column. While iterating from top-left to bottom-right, when we stand in row `i`

, we know the values from the previous row, so, it is enough to update just the elements with value `1`

. We can save the values in a simple array `d[i]`

, `i = 1...m - 1`

, because in the further algorithm we will process the matrix one row at a time and only need the values of the current row.

vector<int> d(m, -1); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 1) { d[j] = i; } } }

### 1.2. Step 2: Problem solving

We can solve the problem in $O(n m^2)$ iterating through rows, considering every possible left and right columns for a submatrix. The bottom of the rectangle will be the current row, and using `d[i][j]`

we can find the top row. However, it is possible to go further and significantly improve the complexity of the solution.

It is clear that the desired zero submatrix is bounded on all four sides by some ones, which prevent it from increasing in size and improving the answer. Therefore, we will not miss the answer if we act as follows: for every cell `j`

in row `i`

(the bottom row of a potential zero submatrix) we will have `d[i][j]`

as the top row of the current zero submatrix. It now remains to determine the optimal left and right boundaries of the zero submatrix, i.e. maximally push this submatrix to the left and right of the `j`

-th column.

What does it mean to push the maximum to the left? It means to find an index `k1`

for which `d[i][k1] > d[i][j]`

, and at the same time `k1`

– the closest one to the left of the index `j`

. It is clear that then `k1 + 1`

gives the number of the left column of the required zero submatrix. If there is no such index at all, then put `k1`

= `-1`

(this means that we were able to extend the current zero submatrix to the left all the way to the border of matrix `a`

).

Symmetrically, you can define an index `k2`

for the right border: this is the closest index to the right of `j`

such that `d[i][k2] > d[i][j]`

(or `m`

, if there is no such index).

So, the indices `k1`

and `k2`

, if we learn to search for them effectively, will give us all the necessary information about the current zero submatrix. In particular, its area will be equal to `(i - d[i][j]) * (k2 - k1 - 1)`

.

How to look for these indexes `k1`

and `k2`

effectively with fixed `i`

and `j`

? We can do that in $O(1)$ on average.

To achieve such complexity, you can use the stack as follows. Let’s first learn how to search for an index `k1`

, and save its value for each index `j`

within the current row `i`

in matrix `d1[i][j]`

. To do this, we will look through all the columns `j`

from left to right, and we will store in the stack only those columns that have `d[][]`

strictly greater than `d[i][j]`

. It is clear that when moving from a column `j`

to the next column, it is necessary to update the content of the stack. When there is an inappropriate element at the top of the stack (i.e. `d[][] <= d[i][j]`

) pop it. It is easy to understand that it is enough to remove from the stack only from its top, and from none of its other places (because the stack will contain an increasing `d`

sequence of columns).

The value `d1[i][j]`

for each `j`

will be equal to the value lying at that moment on top of the stack.

The dynamics `d2[i][j]`

for finding the indices `k2`

is considered similar, only you need to view the columns from right to left.

It is clear that since there are exactly `m`

pieces added to the stack on each line, there could not be more deletions either, the sum of complexities will be linear, so the final complexity of the algorithm is $O(nm)$.

It should also be noted that this algorithm consumes $O(m)$ memory (not counting the input data – the matrix `a[][]`

).

### 1.3. Implementation

int zero_matrix(vector<vector<int>> a) { int n = a.size(); int m = a[0].size(); int ans = 0; vector<int> d(m, -1), d1(m), d2(m); stack<int> st; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 1) d[j] = i; } for (int j = 0; j < m; ++j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d1[j] = st.empty() ? -1 : st.top(); st.push(j); } while (!st.empty()) st.pop(); for (int j = m - 1; j >= 0; --j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d2[j] = st.empty() ? m : st.top(); st.push(j); } while (!st.empty()) st.pop(); for (int j = 0; j < m; ++j) ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1)); } return ans; }