542. 01 Matrix

How to solve 01 Matrix (LeetCode 542): the approach in brief

The problem

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

Pattern

01 Matrix is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph BFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.

Approach outline

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.

Complexity

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

Asked at

01 Matrix has been reported in interviews at Amazon, Google, Microsoft, Uber.