01 Matrix

Medium

BFS

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

This is a multi-source BFS problem. Instead of starting from 1s and searching for 0s, we start from all 0s simultaneously and propagate distances outward. This ensures we find the shortest distance for each cell.

Example 1

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

Output: [[0,0,0],[0,1,0],[0,0,0]]

Explanation: The center cell (1,1) has distance 1 to the nearest 0.

Example 2

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

Output: [[0,0,0],[0,1,0],[1,2,1]]

Explanation: The bottom-center cell (2,1) has distance 2 to the nearest 0.

Constraints

•m == mat.length
•n == mat[i].length
•1 <= m, n <= 10^4
•1 <= m * n <= 10^4
•mat[i][j] is either 0 or 1
•There is at least one 0 in mat

Show Hints (4)

Hint 1: Naive approach: BFS from each cell to find nearest 0. But this is slow.

Hint 2: Better: Multi-source BFS starting from all 0s simultaneously.

Hint 3: Initialize queue with all 0s (distance 0). Mark 1s as unvisited.

Hint 4: Propagate outward - the first time we reach a cell is the shortest distance.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?