Problem Description

You are given an m x n binary matrix mat containing only 0s and 1s. For each cell in the matrix, you need to find the distance to the nearest cell containing a 0.

The distance between two cells is calculated using the Manhattan distance - cells that share a common edge have a distance of 1. This means you can only move horizontally or vertically (not diagonally) from one cell to another, and each such move counts as 1 unit of distance.

For example, if you have a matrix:

1 0 1
1 1 1
0 1 1

The output would be:

1 0 1
2 1 2
0 1 2

Each cell containing a 0 has a distance of 0 to itself. For cells containing 1, the value represents the minimum number of steps needed to reach any cell containing a 0.

The solution uses a multi-source BFS approach. First, all cells containing 0 are added to a queue and marked with distance 0 in the answer matrix. Then, BFS expands outward from all these 0-cells simultaneously, layer by layer. When visiting a cell (i, j), it checks all four adjacent cells. If an adjacent cell hasn't been visited yet (marked as -1), it gets assigned a distance of ans[i][j] + 1 and is added to the queue for further expansion. This ensures that each cell gets the minimum distance to the nearest 0.

The dirs = (-1, 0, 1, 0, -1) pattern with pairwise is a compact way to generate the four directional movements: (-1, 0), (0, 1), (1, 0), (0, -1) for up, right, down, and left respectively.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The matrix can be viewed as a graph where each cell is a node, and adjacent cells (up, down, left, right) are connected by edges. We need to find shortest distances from multiple source nodes (cells with 0) to all other nodes.

Is it a tree?

• No: The matrix graph has multiple paths between cells and can have cycles (you can move in a rectangle and come back to the starting position).

Is the problem related to directed acyclic graphs?

• No: The matrix represents an undirected graph (you can move both ways between adjacent cells), and it can contain cycles.

Is the problem related to shortest paths?

• Yes: We need to find the shortest distance from each cell to the nearest 0. This is a classic shortest path problem.

Is the graph Weighted?

• No: All edges have the same weight of 1 (moving from one cell to an adjacent cell always has a distance of 1).

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the perfect choice. BFS explores nodes level by level, guaranteeing that when we first reach a cell, we've found the shortest path to it.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the shortest distance from each cell to the nearest 0. The multi-source BFS approach is particularly efficient here, starting from all 0-cells simultaneously and expanding outward layer by layer.

Intuition

The key insight is to think of this problem in reverse. Instead of finding the distance from each 1 to the nearest 0, we start from all 0s and expand outward simultaneously.

Imagine dropping stones into water at multiple points - each 0 is like a stone creating ripples. These ripples expand outward at the same speed, and when a ripple reaches a cell for the first time, that's the shortest distance from that cell to any 0.

Why does this work better than starting from each 1? If we started from each 1 and searched for the nearest 0, we'd potentially repeat a lot of work. For a matrix with many 1s and few 0s, we'd be running BFS many times.

By using multi-source BFS starting from all 0s simultaneously, we:

1. Visit each cell exactly once
2. Guarantee that the first time we reach a cell, we've found the shortest path to it
3. Achieve optimal time complexity of O(m × n)

The BFS naturally processes cells in layers:

• Layer 0: All cells containing 0 (distance = 0)
• Layer 1: All cells adjacent to any 0 (distance = 1)
• Layer 2: All cells at distance 2 from the nearest 0
• And so on...

This layer-by-layer expansion ensures that when we first visit a cell, we've found its minimum distance to any 0. We mark visited cells (using ans[x][y] = -1 as "unvisited") to avoid processing them again, which prevents infinite loops and ensures correctness.

Learn more about Breadth-First Search and Dynamic Programming patterns.

Solution Approach

The implementation follows the multi-source BFS pattern we identified:

1. Initialize the answer matrix and queue:

• Create an ans matrix of the same size as mat, initialized with -1 to mark all cells as unvisited
• Create a queue q using deque() for efficient BFS operations
• Traverse the input matrix to find all 0s, set their distance in ans to 0, and add their coordinates to the queue

ans = [[-1] * n for _ in range(m)]
q = deque()
for i, row in enumerate(mat):
    for j, x in enumerate(row):
        if x == 0:
            ans[i][j] = 0
            q.append((i, j))

2. Define directional movements: The code uses a compact pattern to represent four directions:

dirs = (-1, 0, 1, 0, -1)

When paired using pairwise(dirs), this generates: (-1, 0) for up, (0, 1) for right, (1, 0) for down, and (0, -1) for left.

3. Perform BFS expansion:

while q:
    i, j = q.popleft()  # Get current cell
    for a, b in pairwise(dirs):  # Check all 4 directions
        x, y = i + a, j + b  # Calculate neighbor coordinates
        if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
            ans[x][y] = ans[i][j] + 1  # Set distance
            q.append((x, y))  # Add to queue for further expansion

The BFS process:

• Dequeue a cell (i, j) from the front of the queue
• Explore its four adjacent cells
• For each valid, unvisited neighbor (x, y):
  • Mark it as visited by setting ans[x][y] = ans[i][j] + 1
  • Add it to the queue to explore its neighbors in the next layer

4. Return the result: Once the queue is empty, all reachable cells have been assigned their minimum distances, and we return ans.

The time complexity is O(m × n) since each cell is visited at most once, and the space complexity is O(m × n) for the answer matrix and the queue (in the worst case, all cells are 0s).

Example Walkthrough

Let's walk through a small example to illustrate the multi-source BFS approach:

Input matrix:

1 1 0
1 1 1
0 1 1

Step 1: Initialize

• Create ans matrix filled with -1 (unvisited):

-1 -1 -1
-1 -1 -1
-1 -1 -1

• Find all 0s, mark them in ans with distance 0, and add to queue:
  • Found 0 at (0,2): set ans[0][2] = 0, queue = [(0,2)]
  • Found 0 at (2,0): set ans[2][0] = 0, queue = [(0,2), (2,0)]

-1 -1  0
-1 -1 -1
 0 -1 -1

Step 2: BFS Layer 1 (distance = 1)

• Process (0,2): Check neighbors
  • Up: out of bounds
  • Right: out of bounds
  • Down (1,2): unvisited, set ans[1][2] = 1, add to queue
  • Left (0,1): unvisited, set ans[0][1] = 1, add to queue
• Process (2,0): Check neighbors
  • Up (1,0): unvisited, set ans[1][0] = 1, add to queue
  • Right (2,1): unvisited, set ans[2][1] = 1, add to queue
  • Down: out of bounds
  • Left: out of bounds

After Layer 1:

-1  1  0
 1 -1  1
 0  1 -1

Queue = [(1,2), (0,1), (1,0), (2,1)]

Step 3: BFS Layer 2 (distance = 2)

• Process (1,2): Check neighbors
  • Neighbor (1,1) is unvisited, set ans[1][1] = 2, add to queue
  • Other neighbors already visited or out of bounds
• Process (0,1): Check neighbors
  • Neighbor (0,0) is unvisited, set ans[0][0] = 2, add to queue
  • Other neighbors already visited
• Process (1,0): Check neighbors
  • Neighbor (1,1) already set to 2 (reached from another path)
  • Other neighbors already visited
• Process (2,1): Check neighbors
  • Neighbor (2,2) is unvisited, set ans[2][2] = 2, add to queue
  • Other neighbors already visited

After Layer 2:

 2  1  0
 1  2  1
 0  1  2

Queue = [(1,1), (0,0), (2,2)]

Step 4: BFS Layer 3

• Process remaining cells in queue, but all their neighbors are already visited
• Queue becomes empty

Final Result:

2 1 0
1 2 1
0 1 2

Each cell now contains the minimum Manhattan distance to the nearest 0. Notice how the BFS expanded simultaneously from both 0s, and cells were assigned distances based on which source reached them first.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses BFS (Breadth-First Search) starting from all cells containing 0. Each cell in the matrix is visited at most once:

• Initially, we iterate through all m × n cells to find zeros and initialize the answer matrix, which takes O(m × n) time
• During BFS, each cell is added to the queue at most once (when ans[x][y] == -1 is satisfied)
• Each cell is processed (popped from queue) exactly once
• For each processed cell, we check at most 4 neighbors (constant time)

Therefore, the total time complexity is O(m × n).

Space Complexity: O(m × n)

The space usage includes:

• The ans matrix: O(m × n) space to store the distances
• The queue q: In the worst case (when all cells are 0), the queue could contain all m × n cells initially, requiring O(m × n) space
• The dirs tuple uses constant O(1) space

The dominant factor is O(m × n), making the overall space complexity O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Single-Source BFS Instead of Multi-Source BFS

A common mistake is attempting to solve this problem by running BFS from each 1 cell to find the nearest 0. This approach leads to inefficiency and complexity.

Incorrect Approach:

# DON'T DO THIS - Inefficient single-source BFS
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    rows, cols = len(mat), len(mat[0])
    distances = [[0] * cols for _ in range(rows)]
  
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 1:
                # Run BFS from this cell to find nearest 0
                distances[i][j] = self.bfs_to_zero(mat, i, j)
  
    return distances

Why it's problematic:

• Time complexity becomes O(m²n²) in the worst case
• Each 1 cell requires its own BFS traversal
• Redundant computations as multiple cells may explore the same paths

Solution: Use multi-source BFS starting from all 0s simultaneously, as shown in the correct implementation.

2. Incorrect Initialization of the Distance Matrix

Another pitfall is initializing the distance matrix incorrectly, such as using 0 or float('inf') for unvisited cells.

Incorrect:

# Using 0 for unvisited cells - causes confusion with actual 0 distances
distances = [[0] * cols for _ in range(rows)]

# Later in BFS:
if distances[next_row][next_col] == 0:  # Wrong! Can't distinguish between unvisited and distance-0 cells
    distances[next_row][next_col] = distances[current_row][current_col] + 1

Why it's problematic:

• Using 0 makes it impossible to distinguish between cells containing 0 (distance = 0) and unvisited cells
• This leads to incorrect distance calculations or infinite loops

Solution: Use -1 or a separate visited matrix to track unvisited cells clearly.

3. Forgetting to Mark Cells as Visited Before Adding to Queue

Some implementations mark cells as visited after dequeuing rather than before enqueuing.

Incorrect:

while queue:
    current_row, current_col = queue.popleft()
  
    for row_offset, col_offset in directions:
        next_row = current_row + row_offset
        next_col = current_col + col_offset
      
        if (0 <= next_row < rows and 
            0 <= next_col < cols and 
            distances[next_row][next_col] == -1):
          
            queue.append((next_row, next_col))  # Added to queue first
            distances[next_row][next_col] = distances[current_row][current_col] + 1  # Marked after

Why it's problematic:

• The same cell can be added to the queue multiple times from different neighbors
• This doesn't affect correctness (first visit will have minimum distance) but causes unnecessary processing
• Queue can grow larger than necessary, impacting space complexity

Solution: Always mark the cell as visited (update its distance) immediately before adding it to the queue, as shown in the correct implementation.