Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
0 like 0 dislike
289 views
in Coding Questions by Goeduhub's Expert (2.3k points)

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.

Goeduhub's Top Online Courses @Udemy

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
    More Courses

1 Answer

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

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

3.3k questions

7.1k answers

394 comments

4.6k users

Related questions

0 like 0 dislike
1 answer 973 views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 1.2k views
0 like 0 dislike
1 answer 759 views
0 like 0 dislike
1 answer 120 views
0 like 0 dislike
1 answer 511 views

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...