Solution: 01 Matrix
Let's solve the 01 Matrix problem using the Dynamic Programming pattern.
Statement
Given an mat
, find the distance from each cell to the nearest
Constraints:
mat.row
,mat.col
mat.row * mat.col
mat[i][j]
There is at least one
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 (
Using this approach, we can find the minimum distance of every element to its closest
Optimized approach using dynamic programming
Let’s first define our problem in a recursive manner:
The distance of any cell from
can be calculated if we have the minimum distances of all its neighboring cells from . The first base case is that the minimum distance of a cell that contains
itself will be deemed to be . 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
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
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 can be computed by taking the minimum values and then adding . 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:
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
will be the minimum of the cells above and to the left plus . 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
will be the minimum of the cells below it and to its right plus . 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.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.