01 Matrix
Last Updated: March 28, 2026
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 key insight here is about the direction of the search. The naive way is to start from each 1-cell and search outward for the nearest 0. But a much smarter approach is to flip the perspective: start from all the 0-cells and expand outward simultaneously. This way, the first time we reach any 1-cell, we know that is its shortest distance. This "reverse the search direction" idea is the core observation that unlocks the efficient solutions.
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 would be O((m*n)^2) = 10^8, which is borderline.mat[i][j]is either0or1-- Binary values only. We do not need to handle weighted distances.- There is at least one
0inmat-- We are guaranteed a solution exists. No need to handle the impossible case.
Approach 1: BFS from Each Cell (Brute Force)
Intuition
The most straightforward approach: for every cell that contains a 1, start a BFS and expand outward until we hit a 0. The number of steps taken is the distance. Cells that are already 0 get distance 0 immediately.
This works correctly because BFS explores cells layer by layer, so the first 0 we encounter is guaranteed to be the nearest one. The problem is that we are running a separate BFS for every 1-cell, and each BFS could 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
For this brute force approach, the walkthrough is straightforward: for each 1-cell, we run a BFS outward until we find a 0. The BFS for cell (1,1) in mat = [[0,0,0],[0,1,0],[0,0,0]] immediately finds a 0 at distance 1 in all four directions.
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.
For every 1-cell, we launch an independent BFS that potentially scans the entire grid. Many of these BFS runs overlap, doing the same work repeatedly. What if we flipped the direction and searched from all 0-cells outward simultaneously?
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. The first time we reach any 1-cell, the distance recorded is guaranteed to be the shortest, because BFS explores in order of increasing distance.
Think of it like dropping a stone into water at every 0-cell at the same time. The ripples expand outward, and wherever two ripples meet, the closer source wins.
Multi-source BFS is essentially the same as adding a virtual "super source" node connected to all 0-cells with edge weight 0, and then running a standard single-source BFS from that super source. Since BFS explores nodes in order of increasing distance, the first time it reaches any 1-cell, that path length is guaranteed to be the shortest. Every cell is enqueued and dequeued exactly once, so the total work is proportional to 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.
The multi-source BFS is optimal in time but uses O(m * n) extra space for the queue. Can we avoid the queue entirely and achieve the same time complexity with O(1) extra space?
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.
The trick is to split the computation into two passes. 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 considered all four directions, and the result is correct.
Any shortest path from a 1-cell to a 0-cell in a grid can be decomposed into horizontal and vertical moves. The first pass (top-left to bottom-right) correctly computes distances when the nearest 0 is above or to the left. The second pass (bottom-right to top-left) handles cases where the nearest 0 is below or to the right. Since these two passes together cover all four quadrants, the final result is correct. The m + n upper bound works because the maximum possible distance in an m x n grid is m - 1 + n - 1 = m + n - 2, so m + n is always safely larger than any real distance.
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.