Distance of the nearest 1 in a binary matrix

Medium

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]]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}