Distance of nearest cell having 1 | Practice Medium 0 attempts
GeeksforGeeks ↗

Distance of nearest cell having 1 | Practice

Medium Stack&Queue GeeksforGeeks

Given a binary matrix, find the distance of the nearest 1 for each cell. Distance is calculated as the sum of absolute differences of row and column indices.

Example: grid = [[0,0,0],[0,1,0],[1,0,1]] → Output: [[2,1,2],[1,0,1],[0,1,0]]

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N, M <= 500
  • grid[i][j] is 0 or 1
Test Cases
Case 1
Args: [[[0,0,0],[0,1,0],[1,0,1]]] Expected: [[2,1,2],[1,0,1],[0,1,0]]
Topics
Stack&Queue

Multi-source BFS

Start BFS from all cells containing 1 simultaneously.

function nearestCell(grid) {
  const m = grid.length, n = grid[0].length;
  const dist = Array.from({length: m}, () => Array(n).fill(Infinity));
  const q = [];
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (grid[i][j] === 1) { dist[i][j] = 0; q.push([i, j]); }
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  while (q.length) {
    const [r, c] = q.shift();
    for (const [dr, dc] of dirs) {
      const nr = r+dr, nc = c+dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] > dist[r][c]+1) {
        dist[nr][nc] = dist[r][c]+1; q.push([nr, nc]);
      }
    }
  }
  return dist;
}

Time: O(mn) | Space: O(mn)

Saved in this browser only. Private to you.

JavaScript