01 Matrix solution and explanation
Google
9 more videos on this problem
Leetcode 542. 01 Matrix - PythonHelmyCodeCamp · 10:25 · 26K views
01 Matrix | Detailed Dry Run | Why BFS from 0s | GOOGLE | Leetcode - 542codestorywithMIK · 18:59 · 19K views
LeetCode 542. 01 MatrixHappy Coding · 16:55 · 17K views
Amazon Coding Interview Question - 0 1 Matrix - LeetCode 542AlgoJS · 7:55 · 10K views
01 Matrix - Leetcode 542 - PythonTechError · 7:49 · 8K views
01 Matrix (LeetCode 542) | Solution using BFS and Dynamic Programming | 2 sweeps simplifiedNikhil Lohia · 21:27 · 6K views
Mastering LeetCode 542 - 01 Matrix Challenge in Python 🐍 | BFS Deep Dive + Multi-Language SolutionsvanAmsen · 7:44 · 4K views
01 Matrix - LeetCode 542 - Python #leetcode #bfsDeepti Talesra · 18:07 · 2K views
Leetcode 542 01 MatrixJeevan Kumar - Cracckify · 6:18 · 2K views
01 Matrix - LeetCode 542 - Java Breadth First Search - Solution and ExplanationHaddy Ram · 24:57 · 704 views
The problem
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 either0or1.- There is at least one
0inmat.
Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/
Approach overview
Problem Overview: You get an m x n binary matrix containing only 0 and 1. For every cell containing 1, compute the distance to the nearest 0. Distance is measured using 4-directional moves (up, down, left, right). The result is another matrix where each cell stores the shortest distance to a zero.
Approach 1: Breadth-First Search (Multi-Source BFS) (Time: O(m*n), Space: O(m*n))
This problem becomes straightforward once you flip the perspective. Instead of starting BFS from every 1, start from every 0 simultaneously. Push all zero cells into a queue and run a multi-source Breadth-First Search. Each expansion updates neighboring cells with distance current + 1. Because BFS explores level by level, the first time a cell is reached guarantees the shortest path to a zero. Use a queue and iterate through the grid once to initialize it. Then repeatedly pop cells, check their four neighbors, and update distances if they haven't been assigned yet. Each cell enters the queue at most once, giving linear time complexity.
This approach works well because BFS naturally computes shortest paths in an unweighted grid. Since all edges have equal cost (1 step), BFS guarantees minimal distance without extra bookkeeping. For grid shortest-path problems involving nearest targets, multi-source BFS is often the cleanest and most interview-friendly pattern. The grid itself can store distances, so only a queue is required for traversal.
Approach 2: Dynamic Programming Two-Pass Scan (Time: O(m*n), Space: O(1) extra)
The same result can be computed using Dynamic Programming with two directional passes. Initialize a distance matrix with a large value for cells containing 1 and 0 for zero cells. First pass: iterate top-left to bottom-right. For each cell, check top and left neighbors and update the distance using min(current, neighbor + 1). Second pass: iterate bottom-right to top-left and check bottom and right neighbors. These two passes propagate the shortest distance information across the grid.
The key insight is that the shortest path to a zero must come from one of the four directions. Splitting the updates into two directional sweeps ensures all possibilities are covered. This method avoids a queue and works purely with iterative updates over the matrix. Time complexity remains linear because each cell is processed a constant number of times.
Recommended for interviews: Multi-source BFS is the approach most interviewers expect. It demonstrates understanding of grid traversal and shortest-path patterns using BFS. The dynamic programming solution is equally optimal but slightly less intuitive unless you already recognize the two-pass DP pattern used in grid distance problems.
Approach 1: Breadth-First Search (BFS) Approach
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.
from collections import deque
def updateMatrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] > dist[r][c] + 1:
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return distimport java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
Queue<int[]> 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.offer(new int[] {i, j});
} else {
dist[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cell = q.poll();
for (int[] d : directions) {
int r = cell[0] + d[0], c = cell[1] + d[1];
if (r >= 0 && r < m && c >= 0 && c < n && dist[r][c] > dist[cell[0]][cell[1]] + 1) {
dist[r][c] = dist[cell[0]][cell[1]] + 1;
q.offer(new int[] {r, c});
}
}
}
return dist;
}
}#include <vector>
#include <queue>
using namespace std;
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));
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<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c] + 1) {
dist[nr][nc] = dist[r][c] + 1;
q.push({nr, nc});
}
}
}
return dist;
}function updateMatrix(mat) {
const m = mat.length;
const n = mat[0].length;
const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
const queue = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (mat[i][j] === 0) {
dist[i][j] = 0;
queue.push([i, j]);
}
}
}
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length) {
const [row, col] = queue.shift();
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && dist[newRow][newCol] > dist[row][col] + 1) {
dist[newRow][newCol] = dist[row][col] + 1;
queue.push([newRow, newCol]);
}
}
}
return dist;
}#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define QUEUE_SIZE 10000
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
typedef struct {
int row, col;
} Point;
int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = matSize;
*returnColumnSizes = malloc(sizeof(int) * matSize);
int n = matColSize[0];
int** dist = (int**)malloc(sizeof(int*) * matSize);
for (int i = 0; i < matSize; ++i) {
dist[i] = (int*)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
for (int j = 0; j < n; ++j) {
dist[i][j] = mat[i][j] == 0 ? 0 : INT_MAX;
}
}
Point queue[QUEUE_SIZE];
int front = 0, back = 0;
for (int i = 0; i < matSize; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] == 0) {
queue[back++] = (Point){i, j};
}
}
}
while (front < back) {
Point p = queue[front++];
for (int d = 0; d < 4; ++d) {
int r = p.row + directions[d][0];
int c = p.col + directions[d][1];
if (r >= 0 && r < matSize && c >= 0 && c < n && dist[r][c] > dist[p.row][p.col] + 1) {
dist[r][c] = dist[p.row][p.col] + 1;
queue[back++] = (Point){r, c};
}
}
}
return dist;
}using System;
using System.Collections.Generic;
public class Solution {
public int[][] UpdateMatrix(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
int[][] dist = new int[m][];
for (int i = 0; i < m; i++) {
dist[i] = new int[n];
Array.Fill(dist[i], int.MaxValue);
}
Queue<(int, int)> q = new Queue<(int, int)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
q.Enqueue((i, j));
}
}
}
int[][] directions = new int[][] {
new int[] {1, 0},
new int[] {-1, 0},
new int[] {0, 1},
new int[] {0, -1}
};
while (q.Count > 0) {
var (row, col) = q.Dequeue();
foreach (var direction in directions) {
int newRow = row + direction[0], newCol = col + direction[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && dist[newRow][newCol] > dist[row][col] + 1) {
dist[newRow][newCol] = dist[row][col] + 1;
q.Enqueue((newRow, newCol));
}
}
}
return dist;
}
}Python leverages the deque collection for its breadth-first traversal, applying initial zero spotting and neighbor checking in order of distance update efficiency via BFS.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 2: Dynamic Programming Approach
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.
def updateMatrix(mat):
rows, cols = len(mat), len(mat[0])
dist = [[float('inf')] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
else:
if r > 0:
dist[r][c] = min(dist[r][c], dist[r-1][c] + 1)
if c > 0:
dist[r][c] = min(dist[r][c], dist[r][c-1] + 1)
for r in range(rows-1, -1, -1):
for c in range(cols-1, -1, -1):
if r < rows - 1:
dist[r][c] = min(dist[r][c], dist[r+1][c] + 1)
if c < cols - 1:
dist[r][c] = min(dist[r][c], dist[r][c+1] + 1)
return distclass Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[][] dist = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
} else {
dist[i][j] = Integer.MAX_VALUE - 1;
if (i > 0) dist[i][j] = Math.min(dist[i][j], dist[i-1][j] + 1);
if (j > 0) dist[i][j] = Math.min(dist[i][j], dist[i][j-1] + 1);
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i < m - 1) dist[i][j] = Math.min(dist[i][j], dist[i+1][j] + 1);
if (j < n - 1) dist[i][j] = Math.min(dist[i][j], dist[i][j+1] + 1);
}
}
return dist;
}
}#include <vector>
#include <algorithm>
using namespace std;
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 - 1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) dist[i][j] = 0;
else {
if (i > 0) dist[i][j] = min(dist[i][j], dist[i-1][j] + 1);
if (j > 0) dist[i][j] = min(dist[i][j], dist[i][j-1] + 1);
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i < m - 1) dist[i][j] = min(dist[i][j], dist[i+1][j] + 1);
if (j < n - 1) dist[i][j] = min(dist[i][j], dist[i][j+1] + 1);
}
}
return dist;
}function updateMatrix(mat) {
const rows = mat.length, cols = mat[0].length;
const dist = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (mat[r][c] === 0) {
dist[r][c] = 0;
} else {
if (r > 0) dist[r][c] = Math.min(dist[r][c], dist[r-1][c] + 1);
if (c > 0) dist[r][c] = Math.min(dist[r][c], dist[r][c-1] + 1);
}
}
}
for (let r = rows - 1; r >= 0; r--) {
for (let c = cols - 1; c >= 0; c--) {
if (r < rows - 1) dist[r][c] = Math.min(dist[r][c], dist[r+1][c] + 1);
if (c < cols - 1) dist[r][c] = Math.min(dist[r][c], dist[r][c+1] + 1);
}
}
return dist;
}#include <stdio.h>
#include <stdlib.h>
int min(int a, int b) {
return a < b ? a : b;
}
int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {
*returnSize = matSize;
*returnColumnSizes = malloc(sizeof(int) * matSize);
int n = matColSize[0];
int** dist = (int**)malloc(sizeof(int*) * matSize);
for (int i = 0; i < matSize; ++i) {
dist[i] = (int*)malloc(sizeof(int) * n);
(*returnColumnSizes)[i] = n;
for (int j = 0; j < n; ++j) {
dist[i][j] = mat[i][j] == 0 ? 0 : INT_MAX - 1;
}
}
for (int i = 0; i < matSize; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0)
dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
if (j > 0)
dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
}
}
for (int i = matSize - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (i < matSize - 1)
dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
if (j < n - 1)
dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
}
}
return dist;
}public class Solution {
public int[][] UpdateMatrix(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
int[][] dist = new int[m][];
for (int i = 0; i < m; i++) {
dist[i] = new int[n];
for (int j = 0; j < n; j++) {
dist[i][j] = mat[i][j] == 0 ? 0 : int.MaxValue - 1;
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != 0) {
if (i > 0) dist[i][j] = Math.Min(dist[i][j], dist[i - 1][j] + 1);
if (j > 0) dist[i][j] = Math.Min(dist[i][j], dist[i][j - 1] + 1);
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (mat[i][j] != 0) {
if (i < m - 1) dist[i][j] = Math.Min(dist[i][j], dist[i + 1][j] + 1);
if (j < n - 1) dist[i][j] = Math.Min(dist[i][j], dist[i][j + 1] + 1);
}
}
}
return dist;
}
}Python executes a very similar dual-pass strategy, processing twice to cover and update each potential directional influence, ensuring minimal path discovery at each matrix entry point.
Time Complexity: O(m * n)
Space Complexity: O(m * n)
Approach 3: BFS
We create a matrix ans of the same size as mat and initialize all elements to -1.
Then, we traverse mat, adding the coordinates (i, j) of all 0 elements to the queue q, and setting ans[i][j] to 0.
Next, we use Breadth-First Search (BFS), removing an element (i, j) from the queue and traversing its four directions. If the element in that direction (x, y) satisfies 0 leq x < m, 0 leq y < n and ans[x][y] = -1, then we set ans[x][y] to ans[i][j] + 1 and add (x, y) to the queue q.
Finally, we return ans.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns in the matrix mat, respectively.
function updateMatrix(mat: number[][]): number[][] {
const [m, n] = [mat.length, mat[0].length];
const ans: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => -1));
const q: [number, number][] = [];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (mat[i][j] === 0) {
q.push([i, j]);
ans[i][j] = 0;
}
}
}
const dirs: number[] = [-1, 0, 1, 0, -1];
for (const [i, j] of q) {
for (let k = 0; k < 4; ++k) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] === -1) {
ans[x][y] = ans[i][j] + 1;
q.push([x, y]);
}
}
}
return ans;
}func updateMatrix(mat [][]int) [][]int {
m, n := len(mat), len(mat[0])
ans := make([][]int, m)
for i := range ans {
ans[i] = make([]int, n)
for j := range ans[i] {
ans[i][j] = -1
}
}
type pair struct{ x, y int }
var q []pair
for i, row := range mat {
for j, v := range row {
if v == 0 {
ans[i][j] = 0
q = append(q, pair{i, j})
}
}
}
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
for i := 0; i < 4; i++ {
x, y := p.x+dirs[i], p.y+dirs[i+1]
if x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1 {
ans[x][y] = ans[p.x][p.y] + 1
q = append(q, pair{x, y})
}
}
}
return ans
}use std::collections::VecDeque;
impl Solution {
pub fn update_matrix(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let m = mat.len();
let n = mat[0].len();
let mut ans = vec![vec![-1; n]; m];
let mut q = VecDeque::new();
for i in 0..m {
for j in 0..n {
if mat[i][j] == 0 {
q.push_back((i, j));
ans[i][j] = 0;
}
}
}
let dirs = [-1, 0, 1, 0, -1];
while let Some((i, j)) = q.pop_front() {
for k in 0..4 {
let x = i as isize + dirs[k];
let y = j as isize + dirs[k + 1];
if x >= 0 && x < m as isize && y >= 0 && y < n as isize {
let x = x as usize;
let y = y as usize;
if ans[x][y] == -1 {
ans[x][y] = ans[i][j] + 1;
q.push_back((x, y));
}
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n) |
| Dynamic Programming Approach | Time Complexity: O(m * n) |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Multi-Source BFS | O(m*n) | O(m*n) | Best general solution for shortest distance in grids; very intuitive in interviews |
| Dynamic Programming Two-Pass | O(m*n) | O(1) extra | When avoiding queue-based traversal or optimizing memory usage |
Frequently asked questions
Is 01 Matrix easy or hard?
01 Matrix is categorized as a medium problem. The challenge lies in recognizing that BFS should start from all zero cells simultaneously instead of running a search from each one cell. Once that insight is clear, the implementation becomes straightforward.
01 Matrix Python/Java solution
Python and Java solutions typically implement multi-source BFS using a queue. Initialize the queue with all zero cells, then expand in four directions while updating distances. The same logic works across C++, JavaScript, and other languages because it relies on standard queue-based BFS traversal.
How to solve 01 Matrix in O(n)?
Treat the grid as an unweighted graph and run multi-source BFS starting from all zero cells. Each step updates neighbors with distance +1 and pushes them into the queue. Since every cell is visited at most once, the algorithm runs in O(m*n) time, which is linear in the number of cells.
What is the best approach for 01 Matrix?
The most common solution uses multi-source Breadth-First Search. All cells containing 0 are pushed into a queue first, then BFS expands outward to update distances for nearby cells. Because BFS processes nodes level by level, the first distance assigned to each cell is guaranteed to be the shortest. This approach runs in O(m*n) time.
Is 01 Matrix asked at Google/Amazon/Meta?
01 Matrix is a common grid shortest-path problem used by companies such as Amazon, Google, and Meta during coding interviews. It tests BFS fundamentals, matrix traversal, and the ability to recognize multi-source shortest-path patterns.
What data structure is used in 01 Matrix?
The BFS solution uses a queue to process cells in layers while computing shortest distances. The grid or a separate distance matrix stores computed values. The dynamic programming approach instead relies on iterative updates in the matrix without using additional data structures.
What is the time complexity of 01 Matrix?
Both optimal solutions run in O(m*n) time where m and n are the matrix dimensions. Each cell is processed a constant number of times either through BFS traversal or DP updates. Space complexity is O(m*n) for the BFS queue and distance storage, while the DP approach can reduce extra space to O(1).