01 Matrix
The key idea
Run one breadth-first search from ALL the
0 cells at once. Seed the queue with every 0 (distance 0), then expand outward. Because every source starts at the same level, the first time BFS reaches a 1 cell it does so along the shortest path, so that cell's distance is final the moment it is dequeued's neighbor.Problem
Given an m x n binary matrix mat, return a matrix of the same size where each entry is the distance from that cell to the nearest cell containing 0. The distance between two cells that share a side is 1. Every 0 cell has distance 0, and you may assume the matrix contains at least one 0.
Constraints
m == mat.lengthn == mat[i].length1 <= m, n <= 10^41 <= m * n <= 10^4mat[i][j]is either0or1- There is at least one
0inmat
Examples
Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Complexity
Time: O(m * n) Space: O(m * n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY