01 Matrix

mediumGraphs: BFS / DFS205 stepsJava · Python · C++

For every cell, find the distance to the nearest 0. Start a BFS from all zeros at once: the first time the BFS reaches a cell is its shortest distance.

▶ Watch the animated trace

Traced input: mat = [[0, 0, 0], [0, 1, 0], [1, 1, 1]] → [[0, 0, 0], [0, 1, 0], [1, 2, 1]]. Original problem: leetcode.com/problems/01-matrix/

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Each cell is set once.

Key idea

Reverse the question: spread outward from every 0 simultaneously.
Mark 1-cells as unknown (-1) and fill them when first reached.
BFS order guarantees the first visit is the shortest path.

Common mistakes

Running a BFS from each 1 separately is O((m·n)²).
A two-pass DP (top-left, then bottom-right) also works; know it as an alternative.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
int[][] updateMatrix(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    Queue<int[]> queue = new ArrayDeque<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (mat[r][c] == 0) queue.offer(new int[]{r, c});
            else mat[r][c] = -1;
        }
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : DIRS) {
            int r = cell[0] + d[0], c = cell[1] + d[1];
            if (r < 0 || c < 0 || r >= m || c >= n || mat[r][c] != -1) continue;
            mat[r][c] = mat[cell[0]][cell[1]] + 1;
            queue.offer(new int[]{r, c});
        }
    }
    return mat;
}

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def updateMatrix(mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    queue = deque()
    for r in range(m):
        for c in range(n):
            if mat[r][c] == 0: queue.append((r, c))
            else: mat[r][c] = -1
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] == -1:
                mat[nr][nc] = mat[r][c] + 1
                queue.append((nr, nc))
    return mat

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size();
    queue<pair<int, int>> q;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            if (mat[r][c] == 0) q.push({r, c});
            else mat[r][c] = -1;
        }
    while (!q.empty()) {
        auto [r0, c0] = q.front(); q.pop();
        for (auto& d : DIRS) {
            int r = r0 + d[0], c = c0 + d[1];
            if (r < 0 || c < 0 || r >= m || c >= n || mat[r][c] != -1) continue;
            mat[r][c] = mat[r0][c0] + 1;
            q.push({r, c});
        }
    }
    return mat;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single zero far away Distances grow outward from the corner.	`mat = [[1, 1, 1], [1, 1, 1], [1, 1, 0]]`	`[[4, 3, 2], [3, 2, 1], [2, 1, 0]]`
All zeros Every cell is its own nearest zero.	`mat = [[0, 0]]`	`[[0, 0]]`
Single cell Trivial.	`mat = [[0]]`	`[[0]]`