# 01 Matrix Problem

0 like 0 dislike
289 views

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

```Input:
[[0,0,0],
[0,1,0],
[0,0,0]]

Output:
[[0,0,0],
[0,1,0],
[0,0,0]]
```

Example 2:

```Input:
[[0,0,0],
[0,1,0],
[1,1,1]]

Output:
[[0,0,0],
[0,1,0],
[1,2,1]]
```

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

### For Indian Students- INR 360/- || For International Students- \$9.99/-

S.No.

Course Name

Coupon

1.

Tensorflow 2 & Keras:Deep Learning & Artificial Intelligence || Labeled as Highest Rated Course by Udemy

Apply Coupon

2.

Complete Machine Learning & Data Science with Python| ML A-Z Apply Coupon

3.

Complete Python Programming from scratch | Python Projects Apply Coupon

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

We simply do 2 iterations from first to last and last to first element.

For the 1st for loop, we update distance of element with minimum of previous top and left elements + 1 (itself).

For the 2nd for loop, we update distance of element with minimum of previous bottom and right elements + 1 (itself).

As a result, we get minimum distance value for each element updated with distances of neighbours + 1.

class Solution:

def updateMatrix(self, matrix):

m, n = len(matrix), len(matrix and matrix[0])

for i in range(m):

for j in range(n):

if matrix[i][j] != 0:

matrix[i][j] = float("inf")

if i > 0 and matrix[i - 1][j] + 1 < matrix[i][j]:

matrix[i][j] = matrix[i - 1][j] + 1

if j > 0 and matrix[i][j - 1] + 1 < matrix[i][j]:

matrix[i][j] = matrix[i][j - 1] + 1

for i in range(m - 1, -1, -1):

for j in range(n - 1, -1, -1):

if matrix[i][j] != 0:

if i + 1 < m and matrix[i + 1][j] + 1 < matrix[i][j]:

matrix[i][j] = matrix[i + 1][j] + 1

if j + 1 < n and matrix[i][j + 1] + 1 < matrix[i][j]:

matrix[i][j] = matrix[i][j + 1] + 1

return matrix

eg : ans = Solution()

matrix = [[0,0,0], [0,1,0],[0,0,0]]

ans.updateMatrix(matrix)

Output -

[[0,0,0],

[0,1,0],

[0,0,0]]