01 Matrix

Try to solve the 01 Matrix problem.

We'll cover the following

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≤102\leq 10^2

  • 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.

Example#

Created with Fabric.js 3.6.6 Sample Example 1 The value of cell (1,1) in the output is 1, because the minimum distance of all other cells is 0. In any direction,we have to move a distance of 1 toreach the nearest 0.

1 of 3

Created with Fabric.js 3.6.6 Sample Example 2 The value of cell (1,2) in the output should be 2 because the five ways to reach the closest 0 all require moving by two cells.

2 of 3

Created with Fabric.js 3.6.6 Sample Example 3 The value of cell (2,1) in the output should be 2 because the five ways to reach the closest 0 all require moving by two cells.

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

01 Matrix

1

Given a matrix, mat = [[0, 0, 0], [0, 1, 0], [1, 0, 0]], find the matrix that contains the distance of the nearest 0 for each cell.

A)

[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

B)

[[0, 0, 0], [0, 1, 0], [1, 0, 0]]

C)

[[0, 1, 0], [0, 1, 0], [0, 1, 0]]

D)

[[1, 0, 1], [0, 1, 0], [1, 0, 1]]

Question 1 of 30 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Iterate through the matrix and check for the non-zero elements.

At each nonzero element, take the minimum of the element above and to its left and add 1 to the result. Now store the updated result to the current cell.

Traverse the whole matrix from the top-left element to the bottom-right element, and update each nonzero element using the same procedure.

Next, starting from bottom-right element, iterate to the top-left element, looking for even shorter paths to the nearest 0.

While iterating backward, take the minimum of the element below and to the right of the current cell and add 1. Let’s call it the cell’s “candidate distance.”

Then, store the lower of the current cell value and its candidate distance in the current cell.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
01 Matrix

Solution: Climbing Stairs

Solution: 01 Matrix