542. 01 Matrix

01 Matrix (LeetCode 542) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.

How to solve 01 Matrix

01 Matrix is a BFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.

Work towards the solution in these steps:

1. Consider how graph traversal techniques like BFS or DFS can help you explore neighbors in a matrix efficiently.
2. Since you need to find the shortest distance to the nearest zero for each cell, think about starting your search from all zero cells simultaneously rather than from each one individually.
3. Using a queue data structure to perform a multi-source BFS from all zero cells can help you propagate the minimum distance to each cell containing a one.

The reference solution runs in O(m * n) time and O(m * n) space.

The 01 Matrix solution and editorial walks through the full approach with reference code.

Problem statement

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 <= 104

- 1 <= m n <= 104

- 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/

Topics and companies

Topics: Array, Dynamic Programming, Breadth-First Search, Matrix.

Reported in interviews at Amazon, Google, Microsoft, Uber.

How to practise 01 Matrix on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open 01 Matrix in the code editor, or read the 01 Matrix editorial for a worked solution with its approach and complexity analysis.

Where 01 Matrix sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph BFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet

Problems related to 01 Matrix

Other problems that use the same Graph BFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Rotting Oranges — Medium, same subpattern
• Shortest Path in Binary Matrix — Medium, same subpattern
• Walls and Gates — Medium, same subpattern
• Word Ladder — Hard, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern

01 Matrix FAQ