Is 01 Matrix easy or hard?

01 Matrix is categorized as a medium problem. The challenge lies in recognizing that BFS should start from all zero cells simultaneously instead of running a search from each one cell. Once that insight is clear, the implementation becomes straightforward.

01 Matrix Python/Java solution

Python and Java solutions typically implement multi-source BFS using a queue. Initialize the queue with all zero cells, then expand in four directions while updating distances. The same logic works across C++, JavaScript, and other languages because it relies on standard queue-based BFS traversal.

How to solve 01 Matrix in O(n)?

Treat the grid as an unweighted graph and run multi-source BFS starting from all zero cells. Each step updates neighbors with distance +1 and pushes them into the queue. Since every cell is visited at most once, the algorithm runs in O(m*n) time, which is linear in the number of cells.

What is the best approach for 01 Matrix?

The most common solution uses multi-source Breadth-First Search. All cells containing 0 are pushed into a queue first, then BFS expands outward to update distances for nearby cells. Because BFS processes nodes level by level, the first distance assigned to each cell is guaranteed to be the shortest. This approach runs in O(m*n) time.

Is 01 Matrix asked at Google/Amazon/Meta?

01 Matrix is a common grid shortest-path problem used by companies such as Amazon, Google, and Meta during coding interviews. It tests BFS fundamentals, matrix traversal, and the ability to recognize multi-source shortest-path patterns.

What data structure is used in 01 Matrix?

The BFS solution uses a queue to process cells in layers while computing shortest distances. The grid or a separate distance matrix stores computed values. The dynamic programming approach instead relies on iterative updates in the matrix without using additional data structures.

What is the time complexity of 01 Matrix?

Both optimal solutions run in O(m*n) time where m and n are the matrix dimensions. Each cell is processed a constant number of times either through BFS traversal or DP updates. Space complexity is O(m*n) for the BFS queue and distance storage, while the DP approach can reduce extra space to O(1).

Description Solution Video 10:25

542. 01 Matrix

Medium54.7% acceptance14 companies

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 1:

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

Example 2:

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

Constraints:

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

Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/

Asked at 14 companies

Graviton Adobe Flipkart PhonePe DoorDash

Google Amazon Zoho Microsoft Meta Bloomberg Uber

+2 more

Apple LinkedIn

Topics

10:25

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

542. 01 Matrix

Asked at 14 companies

Topics

Similar problems