01 Matrix - Solution & Explanation

Problem Overview: You get an m x n binary matrix containing only 0 and 1. For every cell containing 1, compute the distance to the nearest 0. Distance is measured using 4-directional moves (up, down, left, right). The result is another matrix where each cell stores the shortest distance to a zero.

Approach 1: Breadth-First Search (Multi-Source BFS) (Time: O(m*n), Space: O(m*n))

This problem becomes straightforward once you flip the perspective. Instead of starting BFS from every 1, start from every 0 simultaneously. Push all zero cells into a queue and run a multi-source Breadth-First Search. Each expansion updates neighboring cells with distance current + 1. Because BFS explores level by level, the first time a cell is reached guarantees the shortest path to a zero. Use a queue and iterate through the grid once to initialize it. Then repeatedly pop cells, check their four neighbors, and update distances if they haven't been assigned yet. Each cell enters the queue at most once, giving linear time complexity.

This approach works well because BFS naturally computes shortest paths in an unweighted grid. Since all edges have equal cost (1 step), BFS guarantees minimal distance without extra bookkeeping. For grid shortest-path problems involving nearest targets, multi-source BFS is often the cleanest and most interview-friendly pattern. The grid itself can store distances, so only a queue is required for traversal.

Approach 2: Dynamic Programming Two-Pass Scan (Time: O(m*n), Space: O(1) extra)

The same result can be computed using Dynamic Programming with two directional passes. Initialize a distance matrix with a large value for cells containing 1 and 0 for zero cells. First pass: iterate top-left to bottom-right. For each cell, check top and left neighbors and update the distance using min(current, neighbor + 1). Second pass: iterate bottom-right to top-left and check bottom and right neighbors. These two passes propagate the shortest distance information across the grid.

The key insight is that the shortest path to a zero must come from one of the four directions. Splitting the updates into two directional sweeps ensures all possibilities are covered. This method avoids a queue and works purely with iterative updates over the matrix. Time complexity remains linear because each cell is processed a constant number of times.

Recommended for interviews: Multi-source BFS is the approach most interviewers expect. It demonstrates understanding of grid traversal and shortest-path patterns using BFS. The dynamic programming solution is equally optimal but slightly less intuitive unless you already recognize the two-pass DP pattern used in grid distance problems.