LeetCode 542: 01 Matrix Solution in Python – A Step-by-Step Guide

Imagine you’re navigating a grid of 0s and 1s—like a treasure map where 0s are gold and 1s are empty spaces—and your task is to mark each square with the shortest distance to the nearest gold, like turning a 1 into a 2 if it’s two steps from a 0. That’s the engaging challenge of LeetCode 542: 01 Matrix, a medium-level problem that’s a fantastic way to practice graph traversal in Python. We’ll explore two solutions: the Best Solution, a BFS (breadth-first search) from all 0s that’s efficient and intuitive, and an Alternative Solution, a DFS (depth-first search) with memoization that’s thorough but more complex. With detailed examples, clear code, and a friendly tone—especially for the BFS approach—this guide will help you map those distances, whether you’re new to coding or leveling up. Let’s explore that grid and start measuring!

What Is LeetCode 542: 01 Matrix?

In LeetCode 542: 01 Matrix, you’re given a 2D matrix mat consisting of 0s and 1s, and your task is to return a new matrix of the same size where each cell contains the distance to the nearest 0 in the original matrix, measured as the number of steps (up, down, left, right). For example, with mat = [[0,0,0],[0,1,0],[1,1,1]], the result is [[0,0,0],[0,1,0],[1,2,1]], as each 1 measures its steps to the closest 0. This problem builds on LeetCode 994: Rotting Oranges for BFS techniques in grid traversal.

Problem Statement

Input: mat (List[List[int]])—matrix of 0s and 1s.
Output: List[List[int]]—matrix with distances to nearest 0.
Rules: Distance is number of steps (up, down, left, right); each cell must reflect shortest path to a 0.

Constraints

1 <= m, n <= 10⁴
m * n <= 10⁴
mat[i][j] is 0 or 1.
At least one 0 exists.

Examples

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]

Output: [[0,0,0],[0,1,0],[1,2,1]]
Each 1 finds nearest 0 (e.g., (2,1) → 2 steps to (0,1)).

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]

Output: [[0,0,0],[0,1,0],[0,0,0]]
1 at (1,1) is 1 step from surrounding 0s.

Input: mat = [[1,1,1],[1,1,0]]

Output: [[4,3,2],[3,2,0]]
Distances to (1,2) 0.

Understanding the Problem: Mapping Distances

To solve LeetCode 542: 01 Matrix in Python, we need to compute the shortest distance from each cell to the nearest 0 in a matrix, using only up, down, left, and right moves. A naive approach might calculate distances from each 1 to all 0s (O(m * n * m * n)), but with up to 10⁴ cells, we need efficiency. Since distances spread from 0s, BFS or dynamic programming can optimize this. We’ll explore:

Best Solution (BFS from All 0s): O(m n) time, O(m n) space—fast and optimal.
Alternative Solution (DFS with Memoization): O(m n) time, O(m n) space—thorough but complex.

Let’s dive into the BFS solution with a friendly breakdown!

Best Solution: BFS from All 0s

Why BFS Wins

The BFS from all 0s is the best for LeetCode 542 because it starts from all 0s simultaneously, spreading distances level-by-level to 1s in O(m * n) time and O(m * n) space (queue), ensuring each cell gets its shortest path efficiently. It’s like dropping pebbles (0s) into a pond and watching ripples (distances) reach every shore!

How It Works

Think of this as a distance ripple effect:

Step 1: Initialize Queue:

Add all 0 positions to a queue, mark distances as 0.

Step 2: BFS Traversal:

Process each cell in queue, explore 4 neighbors.
For unvisited 1s, set distance = parent’s + 1, enqueue.

Step 3: Update Matrix:

Fill result matrix with computed distances.

Why It Works:

BFS ensures shortest path (level-order).
Starting from all 0s avoids redundant searches.

It’s like a grid distance spreader!

Step-by-Step Example

Example: mat = [[0,0,0],[0,1,0],[1,1,1]]

Init:

Queue = [(0,0), (0,1), (0,2), (1,0), (1,2)], all 0s.
Distance = [[0,0,0], [0,inf,0], [inf,inf,inf]].

Step 1: BFS:

(0,0): Neighbors (1,0) already 0, skip.
(0,1): (1,1)=1, dist = 1, enqueue (1,1), [[0,0,0], [0,1,0], [inf,inf,inf]].
(0,2): (1,2) already 0, skip.
(1,0): (2,0)=1, dist = 1, enqueue (2,0).
(1,2): (2,2)=1, dist = 1, enqueue (2,2).

Step 2: Process queue:

(1,1): (2,1)=1, dist = 2, enqueue (2,1).
(2,0): (2,1) updated later, skip.
(2,2): No new 1s.
(2,1): Dist = 2, no new 1s.

Result: [[0,0,0],[0,1,0],[1,2,1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

from collections import deque

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])

        # Step 1: Initialize queue and distance matrix
        queue = deque()
        dist = [[float('inf')] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    dist[i][j] = 0
                    queue.append((i, j))

        # Step 2: BFS with 4 directions
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right

        while queue:
            r, c = queue.popleft()
            current_dist = dist[r][c]

            # Explore neighbors
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == float('inf'):
                    dist[nr][nc] = current_dist + 1
                    queue.append((nr, nc))

        # Step 3: Return distance matrix
        return dist

Line 5: Get matrix dimensions.
Lines 8-14: Queue all 0s, initialize distances (inf for 1s, 0 for 0s).
Line 17: Define 4-directional moves.
Lines 19-27: BFS: Pop cell, update unvisited neighbors with +1 distance, enqueue.
Line 30: Return updated matrix.
Time Complexity: O(m * n)—each cell visited once.
Space Complexity: O(m * n)—queue and distance matrix.

It’s like a grid distance rippler!

Alternative Solution: DFS with Memoization

Why an Alternative Approach?

The DFS with memoization solution explores paths from each 1 to the nearest 0, caching distances to avoid recomputation, running in O(m * n) time and O(m * n) space. It’s thorough but less intuitive than BFS, making it a good alternative for DFS learners or when BFS intuition is less clear.

How It Works

Picture this as a grid treasure hunt:

Step 1: Create memoization table.
Step 2: DFS from each 1:

Explore 4 directions, find min distance to 0.
Cache result in table.

Step 3: Build result matrix.

It’s like a grid distance explorer!

Step-by-Step Example

Example: mat = [[0,1],[1,1]]

Init: dp = [[0,inf],[inf,inf]].
DFS (0,1):

Left (0,0)=0, dist = 1, cache 1.

DFS (1,0):

Up (0,0)=0, dist = 1, cache 1.

DFS (1,1):

Up (0,1)=1, Left (1,0)=1, min = 2, cache 2.

Result: [[0,1],[1,2]].

Code for DFS Approach

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])

        # Step 1: Initialize memoization table
        dp = [[float('inf')] * n for _ in range(m)]

        # Step 2: DFS with memoization
        def dfs(r, c):
            if r < 0 or r >= m or c < 0 or c >= n or dp[r][c] != float('inf'):
                return dp[r][c]
            if mat[r][c] == 0:
                dp[r][c] = 0
                return 0

            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            min_dist = float('inf')
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                min_dist = min(min_dist, 1 + dfs(nr, nc))
            dp[r][c] = min_dist
            return min_dist

        # Step 3: Compute distances for all cells
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    dfs(i, j)

        return dp

Line 6: Memoization table with infinity.
Lines 9-20: DFS: Base case at 0 or cached, explore 4 directions, cache min distance.
Lines 23-27: Trigger DFS for each 1.
Time Complexity: O(m * n)—each cell computed once.
Space Complexity: O(m * n)—memoization table.

It’s a DFS distance seeker!

Comparing the Two Solutions

BFS (Best):

Pros: O(m n), O(m n), intuitive shortest path.
Cons: Queue overhead.

DFS (Alternative):

Pros: O(m n), O(m n), thorough.
Cons: Recursive complexity.

BFS wins for clarity and efficiency!

Additional Examples and Edge Cases

[[0]]: [[0]].
[[1]]: [[inf]] (assumes 0 exists, adjust input).
[[0,1,0]]: [[0,1,0]].

BFS handles them all!

Complexity Recap

BFS: Time O(m n), Space O(m n).
DFS: Time O(m n), Space O(m n).

BFS’s the intuitive champ!

Key Takeaways

BFS: Ripple effect—learn at Python Basics!
DFS: Deep dive with cache.
Grids: Distances are fun.
Python: Queues or recursion, your pick!

Final Thoughts: Map Those Distances!

LeetCode 542: 01 Matrix in Python is a delightful grid challenge. BFS from all 0s is your fast track, while DFS with memoization offers a recursive twist. Want more? Try LeetCode 994: Rotting Oranges or LeetCode 200: Number of Islands. Ready to measure? Head to Solve LeetCode 542 on LeetCode and map those distances today!