How do you solve 01 Matrix on LeetCode?

01 Matrix (LeetCode #542) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Using BFS allows us to efficiently find the shortest distance from multiple sources (0s) at once.

What is the brute force solution for 01 Matrix?

The brute force approach for 01 Matrix is Brute Force, with O(m * n * (m + n)) time complexity and O(1) space complexity. For each cell in the matrix, we will calculate the distance to the nearest zero by checking all other cells. This approach is straightforward but inefficient, especially for larger matrices. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve 01 Matrix?

01 Matrix uses the following concepts: Array, Dynamic Programming, Breadth-First Search, Matrix. The recommended patterns to study are: Breadth-First Search, Matrix Traversal.

What are the interview tips for 01 Matrix?

Always consider edge cases, such as matrices with only one row or one column. Explain your thought process clearly; this helps the interviewer understand your approach.

What are common mistakes when solving 01 Matrix?

Not initializing the result matrix correctly, leading to incorrect distance calculations. Forgetting to check bounds when accessing neighboring cells.

#542

01 Matrix

Medium

ArrayDynamic ProgrammingBreadth-First SearchMatrixBreadth-First SearchMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n * (m + n))	O(m * n)
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

We can use a breadth-first search (BFS) approach starting from all the 0s in the matrix. This way, we explore the nearest cells first, ensuring we find the shortest distance efficiently.

⚙️

Algorithm

3 steps

1Step 1: Initialize a queue and add all the positions of 0s in the matrix to it.
2Step 2: Set the distance for all 1s in the result matrix to infinity.
3Step 3: Perform BFS: for each cell, check its neighbors (up, down, left, right) and update their distances if a shorter path is found.

solution.py24 lines

1from collections import deque
2
3def updateMatrix(mat):
4    m, n = len(mat), len(mat[0])
5    result = [[float('inf')] * n for _ in range(m)]
6    queue = deque()
7
8    for i in range(m):
9        for j in range(n):
10            if mat[i][j] == 0:
11                result[i][j] = 0
12                queue.append((i, j))
13
14    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
15
16    while queue:
17        x, y = queue.popleft()
18        for dx, dy in directions:
19            nx, ny = x + dx, y + dy
20            if 0 <= nx < m and 0 <= ny < n and result[nx][ny] > result[x][y] + 1:
21                result[nx][ny] = result[x][y] + 1
22                queue.append((nx, ny))
23
24    return result

ℹ

Complexity note: The time complexity is O(m * n) because we process each cell once. The space complexity is O(m * n) for storing the result and the queue.

1Using BFS allows us to efficiently find the shortest distance from multiple sources (0s) at once.
2The problem can be visualized as a multi-source shortest path problem in an unweighted grid.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.