📖 4 min read
Last updated on

01 Matrix — Coding Interview Walkthrough

By intervu.dev

Hero Image for 01 Matrix — Coding Interview Walkthrough

You’re in a coding interview. The interviewer says: “Given a binary matrix, find the distance of the nearest 0 for each cell.” You know this is BFS, and specifically multi-source BFS, seeded from all 0 cells simultaneously. Starting from 1s and searching for 0s (single-source from each 1) would be much slower. This is LeetCode #542, and the distinction between single-source and multi-source BFS is the entire interview signal.

This walkthrough covers how to recognize multi-source BFS, implement it cleanly, and explain the complexity to your interviewer.

The Problem

Given an m x n binary matrix mat, return a matrix where each cell contains the distance to the nearest 0. Distance is measured in number of steps horizontally or vertically. (LeetCode #542)

Example 1

Input

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

Output

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

Example 2

Input

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

Output

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

Already comfortable with the solution? Practice it in a mock interview →

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Multi-source BFSDo you seed from all 0s simultaneously, not from each 1 separately?
Distance propagationDo you use BFS levels to propagate distances?
Visited trackingDo you use the output distance matrix itself, initializing 1s to infinity?
In-place outputDo you write distances directly into the result matrix?

Step 1: Clarifying Questions

1. Can the matrix contain only 1s? No, there is guaranteed to be at least one 0.

2. Is distance Manhattan or Euclidean? Manhattan (horizontal or vertical steps only, not diagonal).

Step 2: A First (Non-Optimal) Idea

For each 1-cell, run a separate BFS to find the nearest 0. That works, but it’s O(m * n) per 1-cell, giving O((m * n)^2) total. Far too slow for large grids.

ApproachTimeSpace
BFS from each 1O((m*n)^2)O(m*n)

Step 3: The Key Insight

Flip the direction: BFS outward from all 0s simultaneously. Initialize distances of 0-cells to 0 and 1-cells to infinity (or float('inf')). Enqueue all 0-cells at once. BFS propagates distances outward from all 0s in parallel. The first time BFS reaches a 1-cell, that distance is the shortest, guaranteed by BFS’s level-by-level expansion.

3×3 grid showing BFS distance propagation: green 0-cells as seeds, blue cells at distance 1, amber cell at distance 2. ---

Step 4: Algorithm

  1. Create a dist matrix initialized to float('inf') for all cells.
  2. Set dist[r][c] = 0 for every cell where mat[r][c] == 0 and enqueue those cells.
  3. BFS: dequeue a cell, check all 4 neighbors. If dist[neighbor] > dist[current] + 1, update and enqueue.
  4. Return dist.

Python Implementation

from collections import deque

def updateMatrix(mat: list[list[int]]) -> list[list[int]]:
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    # Seed all 0 cells with distance 0
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))

    return dist

Time and Space Complexity

TimeSpace
Multi-source BFSO(m * n)O(m * n)

Every cell is enqueued at most once. The dist matrix serves as both the output and the visited tracker.

Common Interview Mistakes

  • Seeding from 1s instead of 0s. Multi-source BFS from all 1s searching for 0s requires O(n) BFS per 1-cell, totaling O((m*n)^2). Seed from 0s instead.

  • Not initializing 1-cells to infinity. Without a sentinel, you can’t tell which cells have been finalized. Initializing to float('inf') and updating only when an improvement is found is the clean approach.

  • Re-enqueueing cells unnecessarily. The check if dist[nr][nc] > dist[r][c] + 1 prevents redundant enqueuing. If the distance can’t be improved, skip.

What a Strong Candidate Sounds Like

“Multi-source BFS from all 0 cells simultaneously. I initialize the distance matrix to infinity for 1-cells and 0 for 0-cells. BFS expands outward from all 0s in parallel. The first time a 1-cell is reached, that’s its shortest distance. Each cell is processed at most once. O(mn) time and space.”*

Example Interview Dialogue

Interviewer: Why not BFS from each 1 to find its nearest 0?

Candidate: That would be O(mn) per 1-cell, making the total O((mn)^2). Multi-source BFS from all 0s processes every cell exactly once, giving O(m*n) total. The key is that BFS naturally computes shortest paths, so seeding from all 0s at once guarantees each 1-cell gets its shortest distance on first visit.

Practice This in a Mock Interview

01 Matrix is Rotting Oranges with distances instead of times. If you’ve mastered one, the other is a 5-minute adaptation. The core skill is recognizing when to use multi-source BFS.

Start a mock interview for 01 Matrix on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →