Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two cells sharing a common edge is 1.
Example 1:
Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]]
Example 2:
Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.0 in mat.Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/
The goal of #542 01 Matrix is to compute the distance of every cell containing 1 to its nearest 0 in a binary matrix. A common and efficient idea is to treat all 0 cells as starting points and expand outward to update the distance of neighboring cells.
The most popular approach uses multi-source Breadth-First Search (BFS). First, push all cells containing 0 into a queue. Then perform BFS to propagate the shortest distance to adjacent cells. Each step updates neighboring 1 cells with the minimum distance from the nearest zero.
Another approach uses Dynamic Programming with two passes over the matrix. The first pass checks top and left neighbors, while the second pass checks bottom and right neighbors to refine the distances.
Both strategies avoid repeatedly scanning the matrix for each cell. The BFS method is intuitive for shortest-path problems in grids, while the DP method is space-efficient and relies on local transitions.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Multi-source BFS | O(m × n) | O(m × n) |
| Dynamic Programming (Two Pass) | O(m × n) | O(1) extra or O(m × n) depending on implementation |
take U forward
The BFS approach involves initializing a queue with all positions of zeros in the matrix, since the distance from any zero to itself is zero. From there, perform a level-order traversal (BFS) to update the distances of the cells that are accessible from these initial zero cells. This approach guarantees that each cell is reached by the shortest path.
Time Complexity: O(m * n), as each cell is processed at most once.
Space Complexity: O(m * n), for storing the resulting distance matrix and the BFS queue.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define QUEUE_SIZE 10000
6
In the C implementation, we use a queue to perform a BFS starting from all cells with 0. We then update neighboring cells with the smallest distance possible, propagating the minimum distances to eventually fill out the entire matrix with correct values.
The dynamic programming (DP) approach updates the matrix by considering each cell from four possible directions, iterating twice over the matrix to propagate the minimum distances. First, traverse from top-left to bottom-right, and then from bottom-right to top-left, ensuring a comprehensive minimum distance calculation.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, 01 Matrix is a common medium-level interview problem related to graph traversal and dynamic programming. It tests understanding of BFS in grids and optimization techniques for shortest distance problems.
Multi-source BFS allows all zero cells to act as starting points simultaneously. This ensures that each cell gets the minimum distance from the nearest zero while visiting each cell only once.
The optimal approach is usually multi-source BFS. By starting from all cells containing 0 and expanding outward, we compute the shortest distance to each 1 efficiently. This avoids running BFS from every cell individually.
A queue is the key data structure when using the BFS approach. It helps process cells level by level while updating distances to neighboring cells. For the DP approach, the matrix itself stores intermediate distance values.
In this C code, distance calculation progresses first from the top-left to bottom-right. We then perform a second pass from bottom-right to top-left to integrate the shortest distances possible from alternate directions. The use of INT_MAX - 1 is a sufficient surrogate for infinity.