Unraveling the 01 Matrix: Finding the Nearest Zero with BFS and DP

The "01 Matrix" problem (LeetCode 542) is a fundamental challenge that effectively tests your graph traversal and dynamic programming skills. Beyond a typical academic exercise, mastering such problems provides a robust foundation for tackling complex shortest path scenarios in real-world applications, spanning from image processing to logistics. In this post, we will dissect this intriguing problem, explore elegant solutions, and equip you with the knowledge to approach similar challenges confidently.

What is the 01 Matrix Problem?
Approach 1: Multi-Source Breadth-First Search (BFS)
Approach 2: Dynamic Programming (DP)
BFS vs. DP: Which One to Choose?
Conclusion

What is the 01 Matrix Problem?

The "01 Matrix" problem presents a binary matrix, meaning a grid filled with only 0s and 1s. Your task is to transform this matrix into one where each cell indicates the distance to its nearest 0.

Key Definition: The "distance" between two adjacent cells (horizontally or vertically) is 1. We seek the shortest distance, often referred to as the Manhattan distance in a grid context.

Let's illustrate with an example:

Input Matrix:

[[0, 0, 0],
 [0, 1, 0],
 [0, 0, 0]]

Expected Output Matrix:

[[0, 0, 0],
 [0, 1, 0],
 [0, 0, 0]]

Here, the 1 at (1,1) has a 0 directly above, below, left, and right, so its shortest distance to a 0 is 1. All 0s remain 0 as their distance to themselves is 0.

Another example:

Input Matrix:

[[0, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]

Expected Output Matrix:

[[0, 1, 2],
 [1, 2, 3],
 [2, 3, 4]]

Observe how distances increment as you move further away from the initial 0. This problem is essentially a shortest path problem on an unweighted graph where cells are nodes and adjacent cells are edges.

Approach 1: Multi-Source Breadth-First Search (BFS)

BFS is a natural fit for finding the shortest path in an unweighted graph. A key insight here is the presence of multiple sources (all the 0s) from which distances propagate.

The Core Idea

Instead of starting BFS from a single source, we initialize our queue with all the cells that contain a 0. These cells already have a distance of 0. Then, we expand outwards layer by layer, propagating outwards in a layered fashion. Each time we move to an unvisited neighbor, we know its distance is one more than the current cell's distance.

Step-by-Step Breakdown

Initialize dist Matrix: Create a result matrix dist of the same dimensions as the input matrix.
- For cells with 0 in the input, set dist[r][c] = 0.
- For cells with 1 in the input, set dist[r][c] = -1 (or infinity) to mark them as unvisited and to be calculated.
Initialize Queue: Create a queue and add all (r, c) coordinates where matrix[r][c] == 0. These are our starting points.
BFS Traversal:
- While the queue is not empty:
  - Dequeue a cell (r, c).
  - For each of its four neighbors (nr, nc) (up, down, left, right):
    - Check if (nr, nc) is within bounds.
    - If dist[nr][nc] is -1 (indicating it's an unvisited 1):
      - Set dist[nr][nc] = dist[r][c] + 1.
      - Enqueue (nr, nc).
Return dist: The dist matrix now contains the shortest distances.

Python Code Example (Multi-Source BFS)

from collections import deque

def updateMatrixBFS(matrix):
    m, n = len(matrix), len(matrix[0])
    dist = [[-1] * n for _ in range(m)]
    q = deque()

    # Initialize dist matrix and queue with all 0s
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))

    # Directions for neighbors (up, down, left, right)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        r, c = q.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc

            # Check bounds and if neighbor is unvisited (value is -1)
            if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))

    return dist

# Example usage:
matrix1 = [[0,1,1],[1,1,1],[1,1,1]]
print(updateMatrixBFS(matrix1))
# Expected: [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

matrix2 = [[0,0,0],[0,1,0],[0,0,0]]
print(updateMatrixBFS(matrix2))
# Expected: [[0, 0, 0], [0, 1, 0], [0, 0, 0]]

Complexity Analysis (BFS)

Time Complexity: O(M * N), where M is the number of rows and N is the number of columns. Each cell is added to the queue and processed at most once.
Space Complexity: O(M * N) for the dist matrix and, in the worst case, the queue can hold all cells (e.g., a matrix of all 0s or all 1s).

Approach 2: Dynamic Programming (DP)

While BFS is intuitive for shortest paths, dynamic programming offers an alternative perspective, especially useful in grid problems where dependencies are directional. The core principle is that a cell's distance to the nearest 0 depends on its neighbors' distances.

The challenge is that you cannot access all neighbors simultaneously if you are building up the solution. We solve this by doing two passes:

First Pass (Top-Left to Bottom-Right): For each cell, we consider its distance from 0s that are above or to its left. dp[r][c] = min(dp[r][c], dp[r-1][c] + 1, dp[r][c-1] + 1)
Second Pass (Bottom-Right to Top-Left): For each cell, we then refine its distance by considering 0s that are below or to its right. dp[r][c] = min(dp[r][c], dp[r+1][c] + 1, dp[r][c+1] + 1)

Step-by-Step Breakdown

Initialize dp Matrix: Create a dp matrix of the same dimensions.
- If matrix[r][c] == 0, set dp[r][c] = 0.
- If matrix[r][c] == 1, set dp[r][c] to a sufficiently large value (effectively infinity) to represent an unknown, maximum distance.
First Pass (Top-Left to Bottom-Right): Iterate r from 0 to m-1, c from 0 to n-1.
- For dp[r][c], if it's not already 0:
  - If r > 0, dp[r][c] = min(dp[r][c], dp[r-1][c] + 1).
  - If c > 0, dp[r][c] = min(dp[r][c], dp[r][c-1] + 1).
Second Pass (Bottom-Right to Top-Left): Iterate r from m-1 down to 0, c from n-1 down to 0.
- For dp[r][c], if it's not already 0:
  - If r < m-1, dp[r][c] = min(dp[r][c], dp[r+1][c] + 1).
  - If c < n-1, dp[r][c] = min(dp[r][c], dp[r][c+1] + 1).
Return dp: The dp matrix now holds the shortest distances.

Python Code Example (Dynamic Programming)

def updateMatrixDP(matrix):
    m, n = len(matrix), len(matrix[0])

    # Initialize dp matrix with a large value for 1s, 0 for 0s
    # Using m*n as max possible distance (can be optimized to m+n)
    max_dist = m * n 
    dp = [[max_dist] * n for _ in range(m)]

    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 0:
                dp[r][c] = 0
            else:
                # Check top neighbor
                if r > 0:
                    dp[r][c] = min(dp[r][c], dp[r-1][c] + 1)
                # Check left neighbor
                if c > 0:
                    dp[r][c] = min(dp[r][c], dp[r][c-1] + 1)

    # Second pass: bottom-right to top-left
    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            # Check bottom neighbor
            if r < m - 1:
                dp[r][c] = min(dp[r][c], dp[r+1][c] + 1)
            # Check right neighbor
            if c < n - 1:
                dp[r][c] = min(dp[r][c], dp[r][c+1] + 1)

    return dp

# Example usage:
matrix1 = [[0,1,1],[1,1,1],[1,1,1]]
print(updateMatrixDP(matrix1))
# Expected: [[0, 1, 2], [1, 2, 3], [2, 3, 4]]

matrix2 = [[0,0,0],[0,1,0],[0,0,0]]
print(updateMatrixDP(matrix2))
# Expected: [[0, 0, 0], [0, 1, 0], [0, 0, 0]]

Complexity Analysis (DP)

Time Complexity: O(M * N). We iterate through the matrix twice.
Space Complexity: O(M * N) for the dp matrix.

BFS vs. DP: Which One to Choose?

Both BFS and DP provide correct and efficient solutions with the same time and space complexity for this particular problem.

BFS: Often more intuitive for shortest path problems on unweighted graphs. It guarantees finding the shortest path first because it expands layer by layer. The multi-source aspect is handled elegantly.
DP: Requires a bit more thought with the two-pass approach to ensure all dependencies (from all four directions) are covered. However, DP can sometimes be more flexible or adaptable for problems with slightly different constraints or for calculating values beyond just "shortest path."

For the 01 Matrix problem, the Multi-Source BFS is generally considered the more straightforward and natural approach. However, understanding the DP solution broadens your algorithmic toolkit.

Conclusion

The "01 Matrix" problem (LeetCode 542) is an excellent exercise to solidify your understanding of graph traversal algorithms like Breadth-First Search and dynamic programming. Whether you prefer the elegant ripple effect of a multi-source BFS or the methodical two-pass calculation of DP, both methods lead you to the correct shortest distances to the nearest 0.

By mastering problems like this, you are not just solving a LeetCode puzzle; you are building a strong foundation in algorithmic thinking that is invaluable for any coding challenge or real-world system design task. Continue to practice, explore, and enhance your algorithmic proficiency.