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

Distance of nearest cell having 1 | Practice

Medium Stack&Queue GeeksforGeeks

You're given a matrix containing only 0s and 1s. For every cell, compute how far it is from the closest cell holding a 1, where distance between two cells is the Manhattan distance — the sum of the absolute differences between their row indices and their column indices. Return a matrix of these distances.

Input Format
Implement nearestCell(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
grid = [[0,0,0],[0,1,0],[1,0,1]]
Output
[[2,1,2],[1,0,1],[0,1,0]]

Example 2

Input
grid = [[1,1]]
Output
[[0,0]]
Constraints
  • 1 <= rows, cols <= 500
  • grid[i][j] is 0 or 1
  • At least one cell contains 1.
Test Cases (2)
Case 1
Args: [[[0,0,0],[0,1,0],[1,0,1]]] Expected: [[2,1,2],[1,0,1],[0,1,0]]
Case 2
Args: [[[1,1]]] Expected: [[0,0]]
Topics
Stack&Queue

Multi-source BFS

Start BFS from all cells containing 1 simultaneously.

javascript
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]];
  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 && 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