MediumNo. 0542

01 Matrix — LeetCode 542 Python Solution

Topics
Breadth-First Search, Array, Dynamic Programming, Matrix
On a study list
Grind 75
Reading time
3 min

The problem

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two cells sharing a common edge is 1.

Example

Input
mat = [[0,0,0],[0,1,0],[0,0,0]]
Output
[[0,0,0],[0,1,0],[0,0,0]]

Python solution

PythonSolution
class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        ans = [[-1] * n for _ in range(m)]
        q = deque()
        for i, row in enumerate(mat):
            for j, x in enumerate(row):
                if x == 0:
                    ans[i][j] = 0
                    q.append((i, j))
        dirs = (-1, 0, 1, 0, -1)
        while q:
            i, j = q.popleft()
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
                    ans[x][y] = ans[i][j] + 1
                    q.append((x, y))
        return ans

Complexity

Time
O(m × n)
Space · auxiliary
O(m × n)

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 542. 01 Matrix is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 542. 01 Matrix?

LeetCode 542. 01 Matrix is rated Medium on LeetCode.

What is the time complexity of LeetCode 542. 01 Matrix?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 542. 01 Matrix?

The Python solution on this page uses O(m × n) auxiliary space.

What topics does LeetCode 542. 01 Matrix cover?

LeetCode 542. 01 Matrix is tagged Breadth-First Search, Array, Dynamic Programming and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.