01 Matrix
Understanding the Problem
We have a grid of 0s and 1s, and we need to compute a new grid where each cell contains the shortest Manhattan distance to the nearest 0. Cells that are already 0 get distance 0. Cells that are 1 need to find how far away the closest 0 is, counting only horizontal and vertical moves (not diagonal).
The direction of the search determines the cost. Searching outward from each 1-cell for the nearest 0 repeats the same work for every cell. Reversing the direction, starting from all the 0-cells and expanding outward at once, computes every answer in a single sweep: the first time the expansion reaches a 1-cell, that distance is its answer. Both efficient solutions below build on this reversal.
Key Constraints:
1 <= m, n <= 10^4and1 <= m * n <= 10^4: the total number of cells is at most 10,000. A brute force BFS from every cell costs O((m*n)^2), about 10^8 operations, which is borderline.mat[i][j]is either0or1: every move between adjacent cells costs 1, so plain BFS finds shortest distances without a priority queue.- There is at least one
0inmat: every cell has a finite answer, so there is no unreachable case to handle.
Approach 1: BFS from Each Cell (Brute Force)
Intuition
For every cell that contains a 1, start a BFS and expand outward until it reaches a 0. The number of levels traversed is the distance. Cells that are already 0 get distance 0 immediately.
This works because BFS explores cells layer by layer, so the first 0 encountered is the nearest one. The cost comes from running a separate BFS for every 1-cell, where each BFS can visit the entire grid in the worst case.
Algorithm
- Create a result matrix of the same dimensions as
mat. - For each cell (i, j) in the matrix:
- If
mat[i][j] == 0, setresult[i][j] = 0. - Otherwise, run a BFS starting from (i, j). Explore all four neighbors level by level until a cell with value 0 is found. The number of levels traversed is the distance.
- Return the result matrix.
Example Walkthrough
With mat = [[0,0,0],[0,1,0],[1,1,1]], the five 0-cells get distance 0 directly. Each of the four 1-cells gets its own BFS:
The BFS runs for the three bottom-row cells re-scan overlapping neighborhoods of the grid, and none of them reuses anything the others computed.
Code
- Time Complexity: O((m n)^2). For each of the m n cells, we run a BFS that can visit up to m * n cells. In the worst case, every BFS traverses nearly the entire grid.
- Space Complexity: O(m n). Each BFS uses a visited array of size m n, plus the queue can hold up to m * n cells.
Every 1-cell launches an independent BFS, and these runs repeat the same scans over the same regions. The next approach removes the duplication by running one BFS in the opposite direction, from all 0-cells outward at once.
Approach 2: Multi-source BFS (Optimal)
Intuition
Instead of running a separate BFS from each 1-cell, run a single BFS starting from all 0-cells simultaneously. Add every 0-cell to the queue at the start with distance 0, then expand outward layer by layer. Because BFS explores in order of increasing distance, the first time the expansion reaches a 1-cell, the recorded distance is its answer.
An analogy: drop a stone into water at every 0-cell at the same moment. The ripples spread outward, and each cell is claimed by whichever ripple arrives first, which is always the one from the nearest source.
Multi-source BFS is equivalent to adding a virtual "super source" node connected to every 0-cell by a weight-0 edge, then running a standard single-source BFS from that node. The usual BFS guarantee carries over unchanged: cells are dequeued in non-decreasing distance order, so the first distance written to a cell is minimal. Each cell is enqueued at most once, which is what makes the total work linear in the number of cells.
Algorithm
- Create a result matrix initialized to -1 (unvisited).
- Add all cells where
mat[i][j] == 0to the queue and set their distance to 0 in the result matrix. - Process the queue using standard BFS. For each cell dequeued, check all four neighbors.
- If a neighbor has not been visited yet (distance is -1), set its distance to the current cell's distance + 1 and add it to the queue.
- Return the result matrix once the queue is empty.
Example Walkthrough
Code
- Time Complexity: O(m n). Each cell is enqueued and processed exactly once. For each cell, we check at most 4 neighbors. Total work is O(4 m n) = O(m n).
- Space Complexity: O(m n). The distance matrix and the queue can each hold up to m n elements.
Multi-source BFS is optimal in time but allocates a queue that can hold a large fraction of the grid. The final approach keeps the O(m * n) time and replaces the queue with two plain sweeps over the matrix.
Approach 3: Dynamic Programming (Two-Pass)
Intuition
The distance from any cell to the nearest 0 is determined by its neighbors. If a cell is not itself 0, its distance is 1 plus the minimum distance among its four neighbors. The challenge is that we cannot compute all four directions in a single pass because some neighbors have not been computed yet.
Splitting the computation into two passes resolves this. The first pass (top-left to bottom-right) considers the top and left neighbors. The second pass (bottom-right to top-left) considers the bottom and right neighbors. After both passes, every cell has accounted for all four directions.
Because the grid has no obstacles, some shortest path from any cell to its nearest 0 is monotone: it uses at most one vertical direction and one horizontal direction, so it stays in one quadrant relative to the cell. If the nearest 0 lies above and/or to the left, pass 1 computes the distance, because the cells along that monotone path are processed before the cell itself. The symmetric case (below and/or right) is covered by pass 2. The remaining case is a 0 above-right or below-left, where neither pass alone follows the path. Take a 0 above-right and the L-shaped path whose corner sits in the cell's own row: the 0 is straight above that corner, so pass 1 gives the corner its correct value, and pass 2 then carries that value leftward along the row to the cell. The below-left case mirrors this with a corner in the cell's own column. No cell can end up below its true distance, since every value written is 1 plus a neighbor's value and therefore the length of a real path to some 0. The initialization value m + n is safe because no distance in an m x n grid can exceed m + n - 2.
Algorithm
- Create a distance matrix. Set
dist[i][j] = 0for 0-cells anddist[i][j] = m + n(a safe upper bound) for 1-cells. - First pass (top-left to bottom-right): for each cell (i, j) in row-major order, if
i > 0, setdist[i][j] = min(dist[i][j], dist[i-1][j] + 1). Ifj > 0, setdist[i][j] = min(dist[i][j], dist[i][j-1] + 1). - Second pass (bottom-right to top-left): for each cell (i, j) in reverse row-major order, if
i < m-1, setdist[i][j] = min(dist[i][j], dist[i+1][j] + 1). Ifj < n-1, setdist[i][j] = min(dist[i][j], dist[i][j+1] + 1). - Return the distance matrix.
Example Walkthrough
Code
- Time Complexity: O(m n). Two passes over the entire grid, each doing O(1) work per cell. Total: O(2 m n) = O(m n).
- Space Complexity: O(1) extra space. The distance matrix is the output. No queue or auxiliary data structure is needed beyond the output itself.
If mutating the input is acceptable, the same two passes can run directly on mat itself, which removes even the output allocation. The forward-backward sweep also appears outside this problem: image processing calls it a two-pass distance transform (the Chamfer algorithm) and uses it to compute a distance field over an entire image without a queue.