#542

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

01 Matrix

The '01 Matrix' problem challenges you to find the nearest zero for each cell in a binary matrix using dynamic programming.

array dynamic programming breadth first search matrix

Problem Statement

Given a binary matrix mat of size m x n, you need to return a matrix of the same size where each cell contains the distance to the nearest zero. The distance is defined as the number of steps required to travel to a cell containing 0 from the current cell. Only horizontal and vertical moves are allowed.

To achieve this, you must efficiently compute the nearest zero for each cell in the matrix using an optimal approach. The key challenge is managing large matrices with dimensions up to 10^4 x 10^4, so careful attention to time and space complexity is crucial. A state transition dynamic programming method, in conjunction with breadth-first search, can lead to the desired outcome.

Examples

Example 1

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

Output: [[0,0,0],[0,1,0],[0,0,0]]

Example details omitted.

Example 2

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

Output: [[0,0,0],[0,1,0],[1,2,1]]

Example details omitted.

Constraints

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
There is at least one 0 in mat.

Solution Approach

State Transition Dynamic Programming

The key approach to solving this problem involves a dynamic programming technique, where each cell's value is updated to represent the shortest distance from a zero. Start by initializing a matrix with large values and set cells containing zeros to 0. Then, iterate through the matrix to compute the minimal distance by considering neighboring cells.

Breadth-First Search (BFS)

BFS is ideal for this problem as it explores all possible paths from a source cell (zero) and ensures that the closest zero is found first. Starting from all zeros simultaneously, propagate outward to find the nearest zero for every other cell in the matrix. This ensures an efficient O(m*n) time complexity.

Handling Large Matrices

Given the constraints (matrix size up to 10^4 x 10^4), it is essential to optimize both time and space complexity. Using BFS ensures that every cell is visited once, preventing redundant calculations. Additionally, careful memory management is necessary when handling such large inputs, particularly with regard to storing intermediate results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(m n) as every cell is visited once during the BFS process. The space complexity is also O(m n) due to the storage of the distance matrix and BFS queue.

What Interviewers Usually Probe

Candidate is familiar with state transition dynamic programming techniques and can efficiently apply BFS for this type of problem.
Candidate demonstrates an understanding of matrix-based problems and can optimize for large input sizes.
Candidate can explain the trade-offs between time and space complexity in relation to solving matrix problems like '01 Matrix'.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the problem by treating it as a simple DFS or greedy problem instead of applying dynamic programming and BFS.
Not accounting for large input sizes, which could lead to inefficient solutions or memory overflows.
Incorrectly handling edge cases, such as matrices where zeros are scattered in non-trivial patterns.

Follow-up variants

Solving the problem in a 3D matrix or with different distances (e.g., diagonal moves).
Handling non-square matrices or matrices with more complex patterns of zeros.
Optimizing for cases with only one zero in a massive matrix.

FAQ

How do I solve the '01 Matrix' problem?

You can solve it by using a state transition dynamic programming approach with BFS, ensuring that each cell's distance to the nearest zero is calculated efficiently.

What is the time complexity of the '01 Matrix' problem?

The time complexity is O(m*n), as every cell in the matrix is processed once during the BFS traversal.

Can BFS be used for '01 Matrix'?

Yes, BFS is ideal for this problem as it explores all directions from zero and guarantees the shortest path to the nearest zero.

What are the common pitfalls in the '01 Matrix' problem?

Misunderstanding the problem as a greedy or DFS problem, not accounting for large input sizes, and incorrectly handling edge cases are common pitfalls.

What is the primary pattern for solving the '01 Matrix' problem?

The primary pattern for solving this problem is state transition dynamic programming, combined with BFS to propagate the minimal distances efficiently.

terminal

Solution

Solution 1: BFS

We create a matrix $\textit{ans}$ of the same size as $\textit{mat}$ and initialize all elements to $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

Continue Practicing

#329 longest increasing path in a matrix #773 sliding puzzle #1162 as far from land as possible