DSA problem
01 Matrix
Given an m x n binary matrix mat, return a matrix of the same shape where each cell contains the distance to the nearest cell that holds a 0. The distance between two adjacent cells is 1 and movement is restricted to the four cardinal directions.
A first instinct is to run an independent BFS from every cell containing a 1, but that costs O((m * n)^2) in the worst case and is far too slow. The trick is to reverse the direction of the search: instead of asking "how far is each one from the nearest zero", we let every zero broadcast outward simultaneously and let the BFS frontier reach the ones.
This is the same multi-source BFS pattern as Rotting Oranges. Push every zero into the queue with distance 0, mark them as visited (or initialise the answer matrix to 0 for zeros and infinity for ones), then pop cells and relax their neighbours: if a neighbour's current distance can be improved by current + 1, update it and enqueue it. Because BFS visits cells in non-decreasing distance order, every cell is updated to its true shortest distance exactly once.
The resulting algorithm runs in O(m * n) time and O(m * n) extra space (for the queue and the distance matrix). A two-pass dynamic programming variant exists — sweeping top-left to bottom-right then bottom-right to top-left — but BFS is more general and what this category illustrates.
Examples
mat = [[0,0,0],[0,1,0],[0,0,0]][[0,0,0],[0,1,0],[0,0,0]]mat = [[0,0,0],[0,1,0],[1,1,1]][[0,0,0],[0,1,0],[1,2,1]]mat = [[0]][[0]]Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 10^4
- 1 <= m * n <= 10^4
- mat[i][j] is either 0 or 1.
- There is at least one 0 in mat.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.