01 Matrix — Solution in Python, Java & C++
01 Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
01 Matrix is a medium coding problem on arrays, dynamic programming and matrix.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix, Breadth-First Search
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a binary matrix mat, return a matrix of the distance from each cell to the nearest 0 (steps between 4-directionally adjacent cells). The tests guarantee at least one 0.
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
1 <= rows, cols <= 7mat[i][j] is 0 or 1; at least one 0 exists.
Hints for 01 Matrix
Hint 1
Multi-source BFS from every 0 simultaneously.
Hint 2
The BFS wavefront assigns each 1 its distance the first time it's reached.
How to solve 01 Matrix
Running a separate search from every 1 would be quadratic. Invert it: run one BFS seeded with every 0 at once. A multi-source wavefront expanding outward assigns each cell its distance to the nearest source the first time it is reached.
Approach
- Build a distance grid:
0where the input is0, and an "unvisited" marker (say-1) where it is1. - Enqueue every zero cell as a BFS source.
- Pop a cell and look at its four neighbours.
- Any neighbour still marked unvisited gets
dist[current] + 1and joins the queue. - When the queue drains, every cell holds its distance to the nearest zero.
Why it works
BFS from a single source visits cells in non-decreasing distance; with many sources the wavefront is the union of all of them, so the first time a cell is reached is along a shortest path from the closest source. Marking distance at enqueue time is what locks that in — a later, longer path finds the cell already visited and cannot overwrite it. The problem guarantees at least one zero, so every cell is eventually reached.
Complexity
- Time —
O(rows · cols) - Space —
O(rows · cols)
Pitfalls
- Seed all zeros before starting; a per-cell BFS is correct but far slower.
- Use a distinct unvisited marker — initialising distances to
0makes zero cells and unvisited cells indistinguishable. - Set the distance when you enqueue, not when you dequeue, or a cell can be queued several times with different values.
- Only 4-directional moves count as one step.
Reference solution
Python
from typing import List
from collections import deque
def updateMatrix(mat: List[List[int]]) -> List[List[int]]:
R, C = len(mat), len(mat[0])
INF = float("inf")
dist = [[0 if mat[i][j] == 0 else INF for j in range(C)] for i in range(R)]
queue = deque((i, j) for i in range(R) for j in range(C) if mat[i][j] == 0)
while queue:
i, j = queue.popleft()
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if 0 <= ni < R and 0 <= nj < C and dist[ni][nj] > dist[i][j] + 1:
dist[ni][nj] = dist[i][j] + 1
queue.append((ni, nj))
return [[int(x) for x in row] for row in dist]Java
public static int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
int[][] dist = new int[rows][cols];
List<int[]> queue = new ArrayList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
queue.add(new int[]{i, j});
} else {
dist[i][j] = -1;
}
}
}
int head = 0;
while (head < queue.size()) {
int[] cell = queue.get(head++);
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] == -1) {
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
queue.add(new int[]{nr, nc});
}
}
}
return dist;
}C++
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int rows = (int) mat.size(), cols = (int) mat[0].size();
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
vector<vector<int>> dist(rows, vector<int>(cols, -1));
vector<pair<int, int>> queue;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (mat[i][j] == 0) {
dist[i][j] = 0;
queue.push_back(make_pair(i, j));
}
}
}
size_t head = 0;
while (head < queue.size()) {
pair<int, int> cell = queue[head++];
for (int d = 0; d < 4; d++) {
int nr = cell.first + dr[d], nc = cell.second + dc[d];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] == -1) {
dist[nr][nc] = dist[cell.first][cell.second] + 1;
queue.push_back(make_pair(nr, nc));
}
}
}
return dist;
}JavaScript
var updateMatrix = function(mat) {
const R = mat.length, C = mat[0].length;
const dist = mat.map(function(row) {
return row.map(function(v) { return v === 0 ? 0 : Infinity; });
});
let queue = [];
for (let i = 0; i < R; i++) {
for (let j = 0; j < C; j++) {
if (mat[i][j] === 0) queue.push([i, j]);
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0) {
const next = [];
for (const cell of queue) {
for (const d of dirs) {
const ni = cell[0] + d[0], nj = cell[1] + d[1];
if (ni >= 0 && nj >= 0 && ni < R && nj < C && dist[ni][nj] > dist[cell[0]][cell[1]] + 1) {
dist[ni][nj] = dist[cell[0]][cell[1]] + 1;
next.push([ni, nj]);
}
}
}
queue = next;
}
return dist;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming