Solution: 01 Matrix

Let's solve the 01 Matrix problem using the Dynamic Programming pattern.

Statement

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

Constraints:

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

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

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

  • There is at least one 00 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 (11 in this case), we will iterate the whole matrix again and calculate the distance from that 11 to every 00 in the matrix. The distance of that 11 to its closest 00 will be the minimum of all the calculated distances, which will be stored in the cell containing that 11.

Using this approach, we can find the minimum distance of every element to its closest 00. 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×n)2)O((m \times n)^2). The space complexity, on the other hand, will be O(1)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 00 can be calculated if we have the minimum distances of all its neighboring cells from 00.

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

  • 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+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 11 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 00 can be computed by taking the minimum values and then adding 11.

  • 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 00 will be the minimum of the cells above and to the left plus 11.

  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 00 will be the minimum of the cells below it and to its right plus 11. 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.