01 Matrix Problem

Question

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.

Answer 1

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]]