01 Matrix | Leetcode 542 | Explained using BFS

Learn how to solve the “01 Matrix” problem (LeetCode 542) by using a multi-source breadth-first search. We walk through the Python code, explain each step, run a dry example, and analyze complexity.

What the Problem Asks

LeetCode 542: 01 Matrix
Given an m x n binary matrix mat of 0s and 1s, return a matrix dist where dist[i][j] is the distance of the nearest 0 to cell (i, j). Distance is measured in number of steps moving vertically or horizontally.

Input:

• mat: 2D list of integers 0 or 1.

Output:

• 2D list distance of same shape, where each cell holds the minimum distance to any 0 in mat

Intuition & Approach

1. Multi-Source BFS:
   • Instead of running BFS from every 1 cell (which would be slow), we enqueue all 0 cells initially.
   • Then we expand outward in waves. The first time we reach a 1, its distance is the BFS level at which we discover it.
2. Why It Works:
   • BFS guarantees that when a cell is first visited, it’s via the shortest path from any source—in this case, the nearest 0.
3. High-Level Steps:
   • Initialize distance and visited arrays (both zeros).
   • Enqueue every (r, c, dist=0) for which mat[r][c] == 0 and mark visited.
   • While the queue isn’t empty:
     • Pop (i, j, d), set distance[i][j] = d.
     • For each neighbor (ni, nj) in four directions:
       • If it’s in bounds and unvisited, enqueue (ni, nj, d+1) and mark visited.
   • Return distance.

Code Implementation

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        visited = [[0]*cols for _ in range(rows)]
        distance = [[0]*cols for _ in range(rows)]
        queue = deque()

        # 1. Enqueue all zeros as BFS sources
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    queue.append((r, c, 0))
                    visited[r][c] = 1

        # 2. BFS from all zeros simultaneously
        while queue:
            i, j, d = queue.popleft()
            distance[i][j] = d
            # Visit four directions
            for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                ni, nj = i + di, j + dj
                # Skip out of bounds or already visited
                if (0 <= ni < rows and 0 <= nj < cols 
                        and visited[ni][nj] == 0):
                    visited[ni][nj] = 1
                    queue.append((ni, nj, d+1))

        return distance

Step-by-Step Explanation

1. Initialization:
   • visited[r][c] tracks which cells have been enqueued.
   • distance[r][c] will hold the answer for each cell.
   • queue is seeded with all (r, c, 0) where mat[r][c] == 0.
2. Multi-Source BFS:
   • Each dequeued tuple gives us (i, j) plus its distance d from the nearest zero.
   • We record distance[i][j] = d.
   • For each neighbor (ni, nj), if it’s in bounds and not yet visited, we enqueue (ni, nj, d+1)—one step farther from a zero.
3. Completion:
   • When BFS finishes, every cell’s shortest distance to some zero has been set.

Dry Run Example

mat = [
  [0,1,1],
  [1,1,1],
  [1,1,0]
]

1. Enqueue zeros: (0,0,0) and (2,2,0).
2. BFS Level 0:
   • Dequeue (0,0,0), set dist[0][0]=0, enqueue its unvisited neighbors (1,0,1) and (0,1,1).
   • Dequeue (2,2,0), set dist[2][2]=0, enqueue (1,2,1) and (2,1,1).
3. BFS Level 1:
   • Process (1,0,1), (0,1,1), (1,2,1), (2,1,1)—set distances to 1 and enqueue their fresh neighbors with d=2.
4. BFS Level 2:
   • Remaining cell (1,1,2) gets distance 2.
5. Result: csharpCopy[ [0,1,2], [1,2,1], [2,1,0] ]

Time & Space Complexity

• Time Complexity: O(m·n)
  • Each cell is enqueued and processed at most once.
• Space Complexity: O(m·n)
  • The visited and distance arrays plus the BFS queue may all hold O(m·n) elements in the worst case.

Conclusion

By turning every zero into a BFS source and expanding outward, we compute every cell’s distance to the nearest zero in optimal linear time. This “multi-source BFS” pattern is a powerful tool for any grid problem that asks for nearest distances to a set of starting points. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.