01 Matrix
Medium · Graphs · Array · Dynamic Programming · Breadth-First Search · Matrix
Problem
You are given an m x n grid mat of 0s and 1s that contains at least one 0. For every cell, find the distance to the nearest 0, where one step moves to a cell sharing a side. A 0 cell is at distance 0.
Return a grid of the same shape holding those distances.
Examples
Input: mat = [[0,1,1],[1,1,1],[1,1,0]] Output: [[0,1,2],[1,2,1],[2,1,0]]
The center is two steps from either 0; the other corners are two steps from both.
Input: mat = [[1,0],[1,1]] Output: [[1,0],[2,1]]
The bottom-left cell needs two steps to reach the only 0.
Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]
The middle touches a 0 directly; the bottom-middle cell is two steps away.
Constraints
- m == len(mat), n == len(mat[i])
- 1 <= m, n <= 10^4
- 1 <= m · n <= 10^4
- mat[i][j] is 0 or 1
- mat contains at least one 0
Approaches
- Baseline: Manhattan distance to every 0 — time O((m · n)²), space O(m · n)
Follow-up
Without a queue, two sweeps of dynamic programming also work: top-left to bottom-right taking 1 + min(up, left), then bottom-right to top-left taking min(itself, 1 + down, 1 + right). Every shortest path to a 0 bends at most once in each pair of directions, so the two sweeps together see it. If some cells were walls, only the BFS version still works.
Related problems
Start free on Cariara · Coding problems · System design studio
