01 Matrix – Solution & Complexity

Q: What is the time and space complexity of 01 Matrix?

The optimal 01 Matrix solution runs in `O(m*n)` time and `O(m*n)` space. Run a multi-source BFS from every zero at once, assigning each unvisited neighbor its distance the first time it is reached.

Q: What is the most efficient way to solve 01 Matrix?

Run a multi-source BFS from every zero at once, assigning each unvisited neighbor its distance the first time it is reached. This gives `O(m*n)` time complexity, and is a classic matrix, graph, bfs, and queue problem.

Q: How do you solve 01 Matrix in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

We provide a worked 01 Matrix solution in Python, JavaScript, Java, Go, Rust, C++ & Ruby with a step-by-step explanation above. You can also open the interactive editor to write and run your own Python solution against the test cases in the browser.

Q: Is 01 Matrix an easy or hard interview question?

01 Matrix is generally rated **Medium**. It tests matrix, graph, bfs, and queue, which are common coding-interview patterns.

Solution Walkthrough

1. Start with the right graph view

Treat every cell as a graph node with up to four neighbors.
Running a separate shortest-path search from every 1 works, but repeats almost the same exploration many times.
The key insight is to reverse the perspective: start BFS from all zero cells at once, so the first time you reach a cell is automatically its nearest-zero distance.

2. Naive brute force: BFS from each 1-cell

For every cell containing 1, launch a BFS until you touch a 0.
That finds the correct nearest distance for that starting cell, because BFS explores in increasing path length order.
But doing this independently for many cells can degrade to O((m*n)^2) time in the worst case.

from collections import deque

def update_matrix(mat: list[list[int]]) -> list[list[int]]:
    rows = len(mat)
    cols = len(mat[0])
    answer = [[0] * cols for _ in range(rows)]
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    for start_row in range(rows):
        for start_col in range(cols):
            if mat[start_row][start_col] == 0:
                continue

            queue = deque([(start_row, start_col, 0)])
            visited = [[False] * cols for _ in range(rows)]
            visited[start_row][start_col] = True

            while queue:
                row, col, dist = queue.popleft()
                if mat[row][col] == 0:
                    answer[start_row][start_col] = dist
                    break
                for dr, dc in directions:
                    next_row = row + dr
                    next_col = col + dc
                    if (
                        0 <= next_row < rows
                        and 0 <= next_col < cols
                        and not visited[next_row][next_col]
                    ):
                        visited[next_row][next_col] = True
                        queue.append((next_row, next_col, dist + 1))

    return answer

3. Improve it with multi-source BFS

Instead of asking every 1 where its closest 0 is, let every 0 spread outward simultaneously.
Put all zero cells into the queue with distance 0 before the BFS starts.
Then each unvisited neighbor gets distance current + 1; because BFS expands by layers, the first assigned distance is the minimum one.

4. Optimal solution: one BFS from all zeros

Initialize a distance matrix with -1 to mean unvisited.
Seed the queue with every zero cell and mark those distances as 0.
Pop cells in BFS order and assign each unseen neighbor its distance exactly once.

from collections import deque

def update_matrix(mat: list[list[int]]) -> list[list[int]]:
    rows = len(mat)
    cols = len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()

    for row in range(rows):
        for col in range(cols):
            if mat[row][col] == 0:
                dist[row][col] = 0
                queue.append((row, col))

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while queue:
        row, col = queue.popleft()
        for dr, dc in directions:
            next_row = row + dr
            next_col = col + dc
            if (
                0 <= next_row < rows
                and 0 <= next_col < cols
                and dist[next_row][next_col] == -1
            ):
                dist[next_row][next_col] = dist[row][col] + 1
                queue.append((next_row, next_col))

    return dist

5. Dry run on `[[0,0,0],[0,1,0],[1,1,1]]`

Start with every zero already in the queue:

BFS layer	Newly confirmed cells	Distance matrix state
initial	all zeros: `(0,0)`, `(0,1)`, `(0,2)`, `(1,0)`, `(1,2)`	`[[0,0,0],[0,-1,0],[-1,-1,-1]]`
distance 1	`(1,1)`, `(2,0)`, `(2,2)`	`[[0,0,0],[0,1,0],[1,-1,1]]`
distance 2	`(2,1)`	`[[0,0,0],[0,1,0],[1,2,1]]`

The BFS layers stop there, and the final matrix is [[0,0,0],[0,1,0],[1,2,1]].

6. Common mistakes

Running a separate BFS from each 1 in the final solution, which is correct but too slow compared with multi-source BFS.
Forgetting to enqueue all zero cells initially, which breaks the nearest-distance guarantee.
Not marking neighbors as visited when enqueuing them, causing duplicate work or overwritten distances.
Mixing up the four direction deltas or stepping diagonally by accident.

7. Edge cases to test mentally

A matrix that is already all zeros should be returned unchanged.
A 1x1 matrix containing 0 returns [[0]].
Single-row and single-column matrices still work because BFS only uses valid neighbors.
Multiple zeros on different edges should all contribute as simultaneous BFS sources.

8. Final full solution and complexity

Seed the queue with every zero and run one multi-source BFS over the grid. Each cell is enqueued and processed at most once, so the time complexity is O(m*n) and the extra space is O(m*n) for the queue plus distance/visited storage.

from collections import deque

def update_matrix(mat: list[list[int]]) -> list[list[int]]:
    rows = len(mat)
    cols = len(mat[0])
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()

    for row in range(rows):
        for col in range(cols):
            if mat[row][col] == 0:
                dist[row][col] = 0
                queue.append((row, col))

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while queue:
        row, col = queue.popleft()
        for dr, dc in directions:
            next_row = row + dr
            next_col = col + dc
            if (
                0 <= next_row < rows
                and 0 <= next_col < cols
                and dist[next_row][next_col] == -1
            ):
                dist[next_row][next_col] = dist[row][col] + 1
                queue.append((next_row, next_col))

    return dist

01 Matrix – Solution & Complexity

Solution Walkthrough

1. Start with the right graph view

2. Naive brute force: BFS from each 1-cell

3. Improve it with multi-source BFS

4. Optimal solution: one BFS from all zeros

5. Dry run on `[[0,0,0],[0,1,0],[1,1,1]]`

6. Common mistakes

7. Edge cases to test mentally

8. Final full solution and complexity

FAQ

What is the time and space complexity of 01 Matrix?

What is the most efficient way to solve 01 Matrix?

How do you solve 01 Matrix in Python, JavaScript, Java, Go, Rust, C++ & Ruby?

Is 01 Matrix an easy or hard interview question?

See also