Skip to main content

16. 01 Matrix

mediumAsked at JetBrains

Compute the distance from each cell to the nearest 0 — JetBrains uses this to test multi-source BFS, the primitive behind their reachability analyses on call graphs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • mat[i][j] is 0 or 1

Examples

Example 1

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

Example 2

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

Approaches

1. Per-cell BFS

Run BFS from every 1-cell to find its nearest 0; quadratic in cells.

Time
O((mn)^2)
Space
O(mn)
// for each 1-cell, BFS outward until first 0 — repeats work across overlapping frontiers

Tradeoff:

2. Multi-source BFS from all zeros

Seed the queue with every 0 at distance 0, then BFS outward, writing distances as you expand. Linear in cells. Same multi-source-BFS pattern JetBrains uses to compute symbol reachability from entry points.

Time
O(m*n)
Space
O(m*n)
function updateMatrix(mat) {
  const m = mat.length, n = mat[0].length;
  const dist = Array.from({length:m}, () => new Array(n).fill(Infinity));
  const q = [];
  for (let i=0;i<m;i++) for (let j=0;j<n;j++)
    if (mat[i][j]===0) { dist[i][j]=0; q.push([i,j]); }
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length) {
    const [i,j] = q.shift();
    for (const [dx,dy] of dirs) {
      const ni=i+dx, nj=j+dy;
      if (ni<0||nj<0||ni>=m||nj>=n) continue;
      if (dist[ni][nj] > dist[i][j] + 1) { dist[ni][nj] = dist[i][j]+1; q.push([ni,nj]); }
    }
  }
  return dist;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to identify multi-source BFS by name — they value candidates who recognize the same primitive across call-graph reachability, dead-code analysis, and grid distance.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill 01 Matrix and other JetBrains interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →