Problem 21.3 · Breadth-First SearchMedium

01 Matrix

What it teaches: Multi-source BFS from every 0 gives each cell its distance to the nearest 0.

Practise it on judges as “01 Matrix”.

The problem

For each cell of a 0/1 matrix, return the distance (up/down/left/right steps) to the nearest 0.

Example 1

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 ≤ 10⁴
At least one 0

Pattern clues in the wording

→ Distance to the nearest of many targets

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        return mat;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	mat = [[0,0,0],[0,1,0],[0,0,0]]	[[0,0,0],[0,1,0],[0,0,0]]
2	mat = [[0,0,0],[0,1,0],[1,1,1]]	[[0,0,0],[0,1,0],[1,2,1]]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Multi-source BFS from zeros · O(rows × cols)2. Two DP passes · O(rows × cols)

Multi-source BFS from zeros

Time O(rows × cols) Space O(rows × cols)

dist = 0 for zeros (enqueued), −1 for ones. BFS fills each −1 with its parent's distance + 1.

Approach 1

import java.util.*;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] dist = new int[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 0) q.offer(new int[]{r, c});
                else dist[r][c] = -1;
            }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!q.isEmpty()) {
            int[] cell = q.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 || dist[r][c] != -1) continue;
                dist[r][c] = dist[cell[0]][cell[1]] + 1;
                q.offer(new int[]{r, c});
            }
        }
        return dist;
    }
}

Verdict: Each cell is set once.

Two DP passes

Time O(rows × cols) Space O(1) extra

Top-left to bottom-right using up and left neighbours, then bottom-right to top-left using down and right. Each cell ends with min over all four directions.

Approach 2

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length, INF = m + n;
        int[][] d = new int[m][n];
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 0) continue;
                d[r][c] = INF;
                if (r > 0) d[r][c] = Math.min(d[r][c], d[r - 1][c] + 1);
                if (c > 0) d[r][c] = Math.min(d[r][c], d[r][c - 1] + 1);
            }
        for (int r = m - 1; r >= 0; r--)
            for (int c = n - 1; c >= 0; c--) {
                if (r < m - 1) d[r][c] = Math.min(d[r][c], d[r + 1][c] + 1);
                if (c < n - 1) d[r][c] = Math.min(d[r][c], d[r][c + 1] + 1);
            }
        return d;
    }
}

Verdict: No queue; a nice DP view of the same answer.

Before you submit

Edge cases and common mistakes

Test these inputs

All zeros
A single zero in a corner

Mistakes people make

BFS from every 1 separately (O((mn)²)).

Interview

Follow-up questions

What about the farthest water cell from any land (As Far from Land as Possible)?

Command Palette