Solution: 01 Matrix

Statement

Given an $m \times n$ binary matrix, mat, find the distance from each cell to the nearest $0$. The distance between two adjacent cells is $1$. Cells to the left, right, above, and below the current cell will be considered adjacent.

Constraints:

• $1 \leq$ mat.row , mat.col$\leq 10^3$

• $1 \leq$ mat.row * mat.col $\leq 10^4$

• mat[i][j] $\in \{0, 1\}$

• There is at least one $0$ in mat.

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach for this problem is to use a loop to iterate through every element in the matrix, and for every nonzero ($1$ in this case), we will iterate the whole matrix again and calculate the distance from that $1$ to every $0$ in the matrix. The distance of that $1$ to its closest $0$ will be the minimum of all the calculated distances, which will be stored in the cell containing that $1$.

Using this approach, we can find the minimum distance of every element to its closest $0$. However, this approach is very time-consuming. Since we have to iterate over the whole matrix for every nonzero element in the matrix, the time complexity of this approach will be $O((m \times n)^2)$. The space complexity, on the other hand, will be $O(1)$ because no extra space is used.

Optimized approach using dynamic programming

Let’s first define our problem in a recursive manner:

• The distance of any cell from $0$ can be calculated if we have the minimum distances of all its neighboring cells from $0$.

• The first base case is that the minimum distance of a cell that contains $0$ itself will be deemed to be $0$.

• The second base case is that if a nonzero cell is at the boundary of the matrix, we do not consider the directions that lead out of the matrix. For example, if we have a nonzero cell in the first column, we will only consider the cells above and below it (assuming that it isn't at a corner of the matrix) and the cell to its right. If it's in the bottom-left corner, we will only consider the cell above it and to its right.

So, the minimum distance from a nonzero cell to a zero will be the minimum of the distances of its neighboring cells $+1$.

Let’s see how this problem satisfies both conditions of dynamic programming.

• Optimal substructure: If we want to find the minimum distance to the nearest 0 for the cell (i,j), and we know the solution to the cell (i-1, j), cell (i, j-1), cell (i+1,j), and cell (i, j+1), we can take a minimum of these solutions and add $1$ to them. In other words, if the shortest distance to the cells above, below, right, and left have been computed, the shortest distance of the current cell to the nearest $0$ can be computed by taking the minimum values and then adding $1$.

• Overlapping subproblems: In order to calculate the minimum distance of a cell to the nearest 0, we need to evaluate all connecting neighbors of the current cell. If we have already calculated the value of our neighboring cells, we don't want to reevaluate its value. Therefore, we reuse the distances of the closest 0 from the neighboring cells by storing them in the matrix. Since we will be reusing the already evaluated values, this is a typical example of overlapping subproblems. 

There are two steps to solve this problem:

1. We traverse the whole matrix from the element in the top-left corner to the element in the bottom-right corner, checking the element above each nonzero cell and to its left. The minimum distance from the cell to $0$ will be the minimum of the cells above and to the left plus $1$.

2. We traverse the whole matrix in the reverse direction, i.e., from the element in the bottom-right corner to the element in the top-left corner. The minimum distance from the cell to $0$ will be the minimum of the cells below it and to its right plus $1$. Then, we compare this result with the previously stored result in that cell, updating it with the smaller two values.

The slides below illustrate how we would like the algorithm to run.