Distance of the nearest 1 in a binary matrix
Problem
For every cell of a binary matrix, return the distance (in up/down/left/right steps) to the nearest cell containing 1. The LeetCode variant, 01 Matrix, asks for the nearest 0 instead — same method.
Example 1
Input: [[0,1,1,0], [1,1,0,0], [0,0,1,1]] Output: [[1,0,0,1], [0,0,1,1], [1,1,0,0]]
Also asked as: Distance of nearest cell having 1 in a binary matrix
Test cases
Case 1
Input: [[0,1,1,0],[1,1,0,0],[0,0,1,1]] Expected: [[1,0,0,1],[0,0,1,1],[1,1,0,0]]
Case 2
Input: [[1,0,0],[0,0,0]] Expected: [[0,1,2],[1,2,3]]
Case 3
Input: [[1]] Expected: [[0]]
View solutionHide solution1 approach
1. Multi-source BFS from all 1s
Time O(R·C)Space O(R·C)
Push every cell containing 1 with distance 0; BFS outward filling each 0 with its shortest distance.
function nearestOne(grid) { const R = grid.length, C = grid[0].length; const dist = Array.from({ length: R }, () => Array(C).fill(-1)); const q = []; for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (grid[r][c] === 1) { dist[r][c] = 0; q.push([r, c]); } const dirs = [[1,0],[-1,0],[0,1],[0,-1]]; let head = 0; while (head < q.length) { const [r, c] = q[head++]; for (const [dr, dc] of dirs) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nc >= 0 && nr < R && nc < C && dist[nr][nc] === -1) { dist[nr][nc] = dist[r][c] + 1; q.push([nr, nc]); } } } return dist;}