01 Matrix

Medium
121.

01 Matrix

01 Matrix is a medium coding problem on arrays, dynamic programming and matrix.

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 <= 7
  • mat[i][j] is 0 or 1; at least one 0 exists.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 7
  • mat[i][j] is 0 or 1; at least one 0 exists.

Hints for 01 Matrix

  1. Hint 1

    Multi-source BFS from every 0 simultaneously.

  2. 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

  1. Build a distance grid: 0 where the input is 0, and an "unvisited" marker (say -1) where it is 1.
  2. Enqueue every zero cell as a BFS source.
  3. Pop a cell and look at its four neighbours.
  4. Any neighbour still marked unvisited gets dist[current] + 1 and joins the queue.
  5. 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 0 makes 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