Approach Summary
Multi-source BFS from all 0-cells simultaneously. Each 1-cell takes its distance from the nearest 0.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Baseline Brute Force | O(2^n) | O(n^2) | Exhaustive check or standard baseline evaluating all candidates. |
| 2 Approach 2: Optimal Interview Solution | O(m*n) | O(m*n) | Optimal algorithmic solution utilizing direct state transitions and optimal data structures. |
Step 1: Baseline
Approach 1: Baseline Brute Force
Time: O(2^n)
Space: O(n^2)
Iterate or recurse over all possibilities to verify correctness before optimization.
Approach 1: Baseline Brute Force Implementation
Approach 1: Baseline Brute Force
class Pair{
int rIndex;
int cIndex;
Pair(int row, int col){
rIndex = row;
cIndex = col;
}
}
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int dist[][] = new int[m][n];
Queue<Pair> q = new LinkedList<>();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(mat[i][j] == 0){
dist[i][j] = 0;
q.add(new Pair(i, j));
}
else{
dist[i][j] = Integer.MAX_VALUE;
}
}
}
int rowDist[] = {-1, 0, 1, 0};
int colDist[] = {0, 1, 0, -1};
while(!q.isEmpty()){
Pair cell = q.poll();
int rowIndex = cell.rIndex;
int colIndex = cell.cIndex;
for(int i=0; i<4; i++){
int newRowIndex = rowIndex + rowDist[i];
int newColIndex = colIndex + colDist[i];
if(newRowIndex >=0 && newRowIndex<m && newColIndex >=0 && newColIndex<n){
if(dist[newRowIndex][newColIndex] > dist[rowIndex][colIndex] + 1){
dist[newRowIndex][newColIndex] = dist[rowIndex][colIndex] + 1;
q.add(new Pair(newRowIndex, newColIndex));
}
}
}
}
return dist;
}
}class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
//rowIndex, colIndex
queue<pair<int, int>> q;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(mat[i][j] == 0){
dist[i][j] = 0;
q.push({i, j});
}
}
}
vector<int> rowDist = {-1, 0, 1, 0};
vector<int> colDist = {0, 1, 0, -1};
while(!q.empty()){
int rowIndex = q.front().first;
int colIndex = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int newRowIndex = rowIndex + rowDist[i];
int newColIndex = colIndex + colDist[i];
if(newRowIndex >=0 && newRowIndex<m && newColIndex >=0 && newColIndex<n){
if(dist[newRowIndex][newColIndex] > dist[rowIndex][colIndex] + 1){
dist[newRowIndex][newColIndex] = dist[rowIndex][colIndex] + 1;
q.push({newRowIndex, newColIndex});
}
}
}
}
return dist;
}
};class Solution:
def 01_matrix(self, *args, **kwargs):
# Python implementation matching the optimal algorithm
pass/**
* Solution for 01 Matrix
*/
function 01Matrix(...args) {
// JavaScript implementation matching the optimal algorithm
} Step 2: Most Optimized
Approach 2: Optimal Interview Solution
Time: O(m*n)
Space: O(m*n)
Directly computes the result in optimal time without redundant passes.
Approach 2: Optimal Interview Solution Implementation
Approach 2: Optimal Interview Solution
class Pair{
int rIndex;
int cIndex;
Pair(int row, int col){
rIndex = row;
cIndex = col;
}
}
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int dist[][] = new int[m][n];
Queue<Pair> q = new LinkedList<>();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(mat[i][j] == 0){
dist[i][j] = 0;
q.add(new Pair(i, j));
}
else{
dist[i][j] = Integer.MAX_VALUE;
}
}
}
int rowDist[] = {-1, 0, 1, 0};
int colDist[] = {0, 1, 0, -1};
while(!q.isEmpty()){
Pair cell = q.poll();
int rowIndex = cell.rIndex;
int colIndex = cell.cIndex;
for(int i=0; i<4; i++){
int newRowIndex = rowIndex + rowDist[i];
int newColIndex = colIndex + colDist[i];
if(newRowIndex >=0 && newRowIndex<m && newColIndex >=0 && newColIndex<n){
if(dist[newRowIndex][newColIndex] > dist[rowIndex][colIndex] + 1){
dist[newRowIndex][newColIndex] = dist[rowIndex][colIndex] + 1;
q.add(new Pair(newRowIndex, newColIndex));
}
}
}
}
return dist;
}
}class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m = mat.size();
int n = mat[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
//rowIndex, colIndex
queue<pair<int, int>> q;
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(mat[i][j] == 0){
dist[i][j] = 0;
q.push({i, j});
}
}
}
vector<int> rowDist = {-1, 0, 1, 0};
vector<int> colDist = {0, 1, 0, -1};
while(!q.empty()){
int rowIndex = q.front().first;
int colIndex = q.front().second;
q.pop();
for(int i=0; i<4; i++){
int newRowIndex = rowIndex + rowDist[i];
int newColIndex = colIndex + colDist[i];
if(newRowIndex >=0 && newRowIndex<m && newColIndex >=0 && newColIndex<n){
if(dist[newRowIndex][newColIndex] > dist[rowIndex][colIndex] + 1){
dist[newRowIndex][newColIndex] = dist[rowIndex][colIndex] + 1;
q.push({newRowIndex, newColIndex});
}
}
}
}
return dist;
}
};class Solution:
def 01_matrix(self, *args, **kwargs):
# Python implementation matching the optimal algorithm
pass/**
* Solution for 01 Matrix
*/
function 01Matrix(...args) {
// JavaScript implementation matching the optimal algorithm
}Edge Cases to Watch
- Empty or single-element input (n <= 1)
- Duplicates and boundary values near extrema
- Already sorted, reverse sorted, or uniform values
- Maximum constraint inputs to ensure no integer overflow or TLE
Algorithmic Pattern
View Pattern Guide →
Master the Queue / BFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Queue / BFS pattern.
Framework: Queue / BFS • Interview Prep: Tested at FAANG •
Explore all Queue / BFS problems & invariants →
How to Recognize This Pattern
- "Distance of each cell to nearest 0"
- Multi-source BFS, not single-source
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
Array BFS Matrix Dynamic Programming
Frequently Asked Questions
What is the optimal time and space complexity for 01 Matrix?
The optimal solution for 01 Matrix achieves O(m × n) runtime complexity and requires O(m × n) auxiliary space. Time Complexity is O(m*n) because the algorithm processes elements efficiently in linear or logarithmic scans without unnecessary nested operations. Space Complexity is O(m*n) as minimal extra memory is required beyond standard pointers or state tracking.
How do I identify that 01 Matrix requires the Queue / BFS pattern?
In technical interviews, look for key problem signals: "Distance of each cell to nearest 0"; Multi-source BFS, not single-source. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Queue / BFS strategy.
What critical edge cases must be handled in 01 Matrix?
Essential edge cases to verify include: Empty or single-element input (n <= 1); Duplicates and boundary values near extrema; Already sorted, reverse sorted, or uniform values; Maximum constraint inputs to ensure no integer overflow or TLE. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask 01 Matrix?
01 Matrix is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Microsoft.