Given an m x n binary matrix mat, return a matrix of the same size where each cell holds the distance to the nearest 0 in mat. The distance between two neighbouring cells (up, down, left, right) is 1. There is at least one 0 in the matrix.
- 1 <= m, n and m * n <= 10^4
- mat[i][j] is 0 or 1
- At least one 0 exists
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Running a separate BFS from every 1 repeats a lot of work. Turn it around: start one multi-source BFS from all the zeros together. BFS visits cells in order of distance, so the first time a cell is reached, it is reached from its nearest zero, and its distance is the parent's distance plus 1. Every cell is pushed once, so the whole matrix is done in linear time.
Algorithm
- Create
distwith 0 for zero cells and -1 for one cells; push every zero cell into a queue. - Pop a cell and look at its 4 neighbours.
- For each neighbour with
dist == -1, setdist = dist[cur] + 1and push it. - When the queue is empty, return
dist.
O(m * n)Space: O(m * n)class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) dist = [[-1] * n for _ in range(m)] # -1 means not reached yet queue = deque() for r in range(m): for c in range(n): if mat[r][c] == 0: dist[r][c] = 0 queue.append((r, c)) # all zeros are sources while queue: r, c = queue.popleft() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) return dist