01 Matrix

01 Matrix

What is this problem about?

The 01 Matrix interview question asks you to take a binary matrix (consisting of 0s and 1s) and calculate the distance of the nearest 0 for each cell. If a cell contains a 0, the distance is naturally 0. If it contains a 1, you must find the shortest path (moving up, down, left, or right) to any cell containing a 0.

Why is this asked in interviews?

Companies like Google, Meta, and Amazon favor this problem because it tests your ability to handle multi-source shortest path problems. While a single-source search is common, the 01 Matrix coding problem requires you to efficiently process multiple starting points simultaneously, demonstrating a deep understanding of graph traversal efficiency.

Algorithmic pattern used

The most efficient approach follows the Breadth-First Search (BFS) interview pattern. Specifically, it uses a Multi-Source BFS. Instead of starting a BFS from every '1' (which would be too slow), you start by adding all '0's to a queue and "radiating" outward. Alternatively, it can be solved using Dynamic Programming by performing two passes (top-left to bottom-right and vice versa) to propagate minimum distances.

Example explanation

Imagine a 3x3 grid:

1 1 1
1 1 1
0 1 1

The only 0 is at the bottom-left $(2,0)$.

• Its immediate neighbors $(1,0)$ and $(2,1)$ are 1 step away.
• Cells $(0,0)$, $(1,1)$, and $(2,2)$ are 2 steps away.
• The furthest cell $(0,2)$ is 4 steps away. The output matrix replaces each '1' with its calculated distance.

Common mistakes candidates make

• Starting BFS from '1's: If you start a new BFS for every '1' in the matrix, your time complexity will skyrocket to $O((M \times N)^2)$, which will fail on large test cases.
• Ignoring boundaries: Forgetting to check if a neighbor is within the matrix bounds before adding it to the queue.
• Not marking visited cells: In BFS, failing to track which cells have already been processed leads to infinite loops or redundant calculations.

Interview preparation tip

Whenever you see a grid problem asking for the "shortest distance" to a specific set of targets, think Multi-Source BFS first. It’s almost always more performant than repetitive DFS or standard DP.