Skip to content

542. 01 Matrix

Difficulty Topics

Description

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

 

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

 

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • There is at least one 0 in mat.

Solution

01-matrix.py
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        queue = collections.deque()

        for x in range(rows):
            for y in range(cols):
                if mat[x][y] == 0:
                    queue.append((x, y))
                else:
                    mat[x][y] = float('inf')

        while queue:
            x, y = queue.popleft()

            for dx,dy in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
                if 0 <= dx < rows and 0 <= dy < cols and mat[x][y] < mat[dx][dy]:
                    queue.append((dx, dy))
                    mat[dx][dy] = mat[x][y] + 1

        return mat