• m == mat.length, n == mat[i].length
• 1 <= m, n <= 10⁴
• 1 <= m × n <= 10⁴
• mat[i][j] is 0 or 1
• At least one 0 is present, so every cell has a finite answer.

The question asks for a distance, and the distance of every cell, which is more than a single shortest-path query. So the first decision is not how to search but which direction to search in — and getting that backwards is what separates a solution that runs instantly from one that times out.

Take each cell containing a 1, and search outward from it until you bump into a 0. Expanding in rings from a starting cell finds the nearest 0 correctly, since the first 0 encountered is by construction the closest one.

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    out = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 1:
                out[r][c] = bfs_to_nearest_zero(mat, r, c)   # a whole search, per cell
    return out

Correct, and quadratic. Each search can sweep the entire matrix before finding a 0 — imagine a huge field of 1s with a single 0 in a far corner — so with up to m × n cells each running a search costing up to m × n, the total is O((m × n)²). At the constraint limit of 10⁴ cells that is 10⁸ operations for a problem that should take 10⁴.

Look closely at what is repeated. Two adjacent 1s run two separate searches that sweep almost exactly the same territory and arrive at almost exactly the same 0. Every cell in a large region of 1s rediscovers the same geography. Thousands of searches are converging on the same handful of destinations.

That phrasing points straight at the fix. When many searchers are all trying to reach the same few places, stop searching from the many and start searching from the few.

Instead of each 1 hunting for a 0, let every 0 broadcast outward simultaneously.

Seed a search with all the zero cells at once, all at distance 0. Expand in rings: every unclaimed cell adjacent to the seeds is at distance 1, every unclaimed cell adjacent to those is at distance 2, and so on until the matrix is covered.

Why does this give each cell its distance to its nearest 0 rather than to some arbitrary 0? Because all the sources start together and the rings advance in lockstep. A cell at true distance d from its nearest 0 cannot be claimed before ring d — being claimed at ring d′ < d would mean a chain of d′ steps back to some 0, contradicting d being the minimum. And it cannot be claimed after ring d, because the neighbour of it that lies at distance d−1 gets expanded during ring d−1 and claims it immediately. So each cell is claimed in exactly the right ring, by whichever source happens to be nearest.

This is multi-source Breadth-First Search, and the key realisation is that it is not many searches — it is one search whose distance-0 layer simply has many members. It costs the same as a single-source search.

The reversal itself is the transferable move. Asking "how far is each cell from the nearest source?" is many-to-few, which is expensive from the cell side and cheap from the source side. Whenever a problem asks for a distance to the nearest member of a set, reverse the direction and broadcast from the set.

A queue holds the frontier and hands cells back in discovery order; that FIFO discipline is what keeps ring d fully processed before ring d+1 starts. A stack would let one branch race ahead and distances would come out wrong.

The distance matrix itself doubles as the record of what has been claimed: a cell still holding the sentinel has not been reached yet, so no separate visited structure is needed.

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]      # -1 means "not reached yet"
    queue = deque()

    for r in range(rows):                          # seed every zero at once
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    while queue:
        r, c = queue.popleft()
        for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1      # claim on discovery
                queue.append((nr, nc))
    return dist

Note there is no explicit ring counter and no frozen queue length here, unlike problems that need to report elapsed time. Each cell simply inherits its parent's distance plus one, which is equivalent and simpler when the answer is a per-cell value rather than a count of rounds.

Setup seeds the five zeros — (0,0), (0,1), (0,2), (1,0) and (1,2) — each at distance 0. The four ones at (1,1), (2,0), (2,1) and (2,2) hold −1.

Result: [[0,0,0],[0,1,0],[1,2,1]]. The centre cell (2,1) is 2 because its three orthogonal neighbours are all 1s and it must travel two steps in any direction to escape the bottom row.

There is a subtle property of this specific problem: since the 1s are not obstacles, any cell may be walked through, so the distance between two cells is just the Manhattan distance |Δrow| + |Δcolumn|, and the answer for a cell is the minimum of that over all zeros. Nothing has to be routed around.

That regularity permits a solution with no queue at all. Sweep the matrix twice.

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    BIG = rows + cols                                # larger than any real distance
    dist = [[0 if v == 0 else BIG for v in row] for row in mat]

    for r in range(rows):                            # pass 1: top-left to bottom-right
        for c in range(cols):
            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):                # pass 2: bottom-right to top-left
        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 dist

The reasoning: any shortest path to a nearest 0 is monotone in the sense that it can be split into a portion using only up-and-left moves and a portion using only down-and-right moves. The first pass propagates the best distance obtainable from above or from the left; the second pass folds in the best from below or the right. Together they cover every direction, so after both passes each cell holds the true minimum.

The second pass must run in reverse order, and that is not stylistic — it is required so that dist[r+1][c] has already been finalised for the downward direction before dist[r][c] reads it. Running it forwards would read values not yet updated.

Same O(m × n) bound, but no queue and no extra memory beyond the output. It is faster in practice thanks to sequential memory access. The catch is that it depends entirely on there being no obstacles — introduce impassable cells and the monotone-path argument breaks, while multi-source BFS keeps working unchanged. That contrast is the useful thing to be able to say out loud.

Train two reflexes here. First: when a problem asks for the distance from every cell to the nearest member of some set, flip the search direction and broadcast from the set — one multi-source pass replaces thousands of individual searches, and the wave arrives at each cell from its nearest source automatically. Second: read carefully whether the marked cells are obstacles or merely targets. Here they are targets, which is what makes the distances Manhattan and unlocks the two-pass alternative. The same grid with obstacles is an entirely different problem, and the BFS is the version that survives the change.