DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

01 Matrix

mediumGraphs

Problem statement

You get an m x n matrix mat of 0s and 1s, containing at least one 0. For every cell, find the distance to the nearest 0, where one step moves up, down, left or right to a neighbouring cell.

Return a matrix of the same size holding those distances. Cells that are already 0 have distance 0.

Examples

Example 1

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

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

Explanation: The edge midpoints are one step from the centre; the corners need two.

Example 2

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

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

Hints

Approach

Two dynamic-programming sweeps. A 1 cell's distance is one more than the best of its four neighbours, but a single sweep only has final values for the neighbours it has already visited, so do two sweeps in opposite directions.

  1. Set zeros to 0 and every other cell to a large value (rows + cols is larger than any real distance).
  2. Sweep top-left to bottom-right. Each cell becomes the minimum of itself and 1 + its top and left neighbours.
  3. Sweep bottom-right to top-left. Each cell becomes the minimum of itself and 1 + its bottom and right neighbours.

After both passes, every cell has considered paths from all four directions. Same O(m * n) time as BFS, but the only memory beyond the output matrix is a few variables: no queue.

ComplexityTime O(m * n)Space O(1) extra
Python
class Solution:
def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
rows, cols = len(mat), len(mat[0])
far = rows + cols
dist = [[0 if v == 0 else far for v in row] for row in mat]
for r in range(rows): # from top-left
for c in range(cols):
if r > 0:
dist[r][c] = min(dist[r][c], dist[r - 1][c] + 1)
if c > 0:
dist[r][c] = min(dist[r][c], dist[r][c - 1] + 1)
for r in range(rows - 1, -1, -1): # from bottom-right
for c in range(cols - 1, -1, -1):
if r < rows - 1:
dist[r][c] = min(dist[r][c], dist[r + 1][c] + 1)
if c < cols - 1:
dist[r][c] = min(dist[r][c], dist[r][c + 1] + 1)
return dist

Follow-up questions

  • Some cells are walls that cannot be crossed. Which approach still works?
  • Moves may also go diagonally at cost 1. What changes?

Frequently asked questions

If the nearest zero is up-left, the first pass finds it; if it is down-right, the second pass does. For a zero up-right, the first pass gives the correct value to the cell directly below that zero in your row, and the second pass then carries it leftwards to you. Down-left works the same way through your column.

Lead with multi-source BFS: it is the general technique and still works with obstacles. Mention the two-pass DP as the space improvement for an open grid. The DP breaks if walls are added, because a shortest path may then need to change direction more than once.

Multi-source BFS is how you answer "how many hops is each node from the nearest healthy replica, cache or egress point?" in a network: seed the search with every source at once instead of searching from every node.