Medium

01 Matrix

LAB

Given a binary matrix, return a matrix where each cell stores its distance to the nearest zero.

EXAMPLES

Example 1

Input
{
  "mat": [
    [
      0,
      0,
      0
    ],
    [
      0,
      1,
      0
    ],
    [
      1,
      1,
      1
    ]
  ]
}

Output
[
  [
    0,
    0,
    0
  ],
  [
    0,
    1,
    0
  ],
  [
    1,
    2,
    1
  ]
]

FUNCTION SHAPE

mat: intMatrix→intMatrix

SOLUTION NOTE

Two-pass grid DP: the forward pass sees nearest zeros from top/left, and the backward pass sees nearest zeros from bottom/right. Multi-source BFS is another valid source-backed solution.

Reveal reference solution +

pythonREFERENCE

def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    INF = m + n + 1
    dist = [[0 if mat[i][j] == 0 else INF for j in range(n)] for i in range(m)]

    for i in range(m):
        for j in range(n):
            if i > 0:
                dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
            if j > 0:
                dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if i + 1 < m:
                dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
            if j + 1 < n:
                dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)

    return dist

TimeO(m × n)

SpaceO(m × n)

Open on LeetCode ↗