Problem overview
The method computeGrid receives a matrix of 0s and 1s as a number[][]. For every cell it must find the distance to the nearest 0, where moving to an adjacent cell (up, down, left or right) costs 1. It returns a matrix of the same shape holding those distances. The matrix has at least one 0, and its total number of cells is at most 10,000.
Take the second example:
0 0 0 0 0 0
0 1 0 -> 0 1 0
1 1 1 1 2 1
Every 0 is at distance 0 from itself. The 1 in the middle has a 0 right beside it, so its distance is 1. The bottom-left and bottom-right 1s each touch a 0 above them, so they are 1 as well. The bottom-middle 1 has no 0 next to it: its nearest 0 is two steps away, so it becomes 2.
Approach: start the search from all zeros at once
The direct approach runs a search from every 1 until it finds a 0. With up to 10,000 cells, that repeats a lot of work. The idea that removes the repetition is to turn the problem around: instead of asking each 1 for its nearest 0, let every 0 spread outward at the same time.
This is a multi-source breadth-first search. Put all the zeros in the queue first, each with distance 0. Then process the queue in order. Cells leave the queue in order of increasing distance, so the first time the search reaches a cell, it comes from the nearest 0 and the cell's distance is final. A cell labeled this way is never visited again, so the whole grid is handled in one pass.
The grid itself serves as the visited marker. Before the search starts, every 1 is replaced with -1, meaning "distance not known yet". A neighbour is worth visiting only while it still holds -1. Distances are never negative, so there is no confusion between the marker and a real answer.
Step by step
- Create the queue as an empty
number[][]calledque. Each entry is a[row, column]pair. - Store the dimensions in
n(rows,grid.length) andm(columns,grid[0].length). The bounds checks later stay short. - Scan all cells with nested loops over
iandj. - Enqueue every zero. If
grid[i][j]is 0, push[i, j]. Its distance is already right. - Mark every other cell by setting it to
-1. - List the four moves as a
constarray of row and column offsets: up, down, left and right. - Loop while the queue has entries.
- Take the front pair with
shift()and destructure it intox1andy1. Taking from the front is what keeps the order by distance. - Try each move. Destructure each offset into
dxanddyand compute the neighbour(x2, y2). - Check the bounds and the marker. The neighbour must be inside the grid and still be
-1. - Label and enqueue it. Set the neighbour to
grid[x1][y1] + 1, then push[x2, y2], so its own neighbours get their turn. - Return
grid, which now holds the distances.
The solution in TypeScript
class Solution {
computeGrid(grid: number[][]): number[][] {
let que: number[][] = [];
let n = grid.length, m = grid[0].length;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (grid[i][j] == 0) {
que.push([i, j]);
} else {
grid[i][j] = -1;
}
}
}
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
while (que.length > 0) {
let [x1, y1] = que.shift();
for (let [dx, dy] of directions) {
let x2 = x1 + dx;
let y2 = y1 + dy;
if (0 <= x2 && x2 < n && 0 <= y2 && y2 < m && grid[x2][y2] == -1) {
grid[x2][y2] = grid[x1][y1] + 1;
que.push([x2, y2]);
}
}
}
return grid;
}
}
Details worth knowing:
- Destructuring a shifted pair.
let [x1, y1] = que.shift();unpacks the two numbers. The type ofshift()isnumber[] | undefined. The lessons compile with strict checks turned off, which is why this line is accepted without a!. UnderstrictNullChecksthe compiler would complain, andque.shift()!would be the fix. - Destructuring in a
for...ofheader.for (let [dx, dy] of directions)gives each move's two offsets their own names. - No chained comparisons. Python allows
0 <= x2 < n, but in TypeScript that means something different:0 <= x2gives a boolean, which is then compared withn. Each bound is therefore a separate comparison joined with&&. - Order inside the condition. The bounds are tested before
grid[x2][y2]. Ifx2were-1,grid[-1]would beundefinedand indexing it would throw. The&&chain stops before that happens. - The input is changed. The returned matrix is the same array that was passed in. Copy the matrix first if the caller still needs the original 0s and 1s.
shiftis not free. Removing from the front of an array shifts the remaining items in principle, but for grids of this size it is fast enough.
Complexity
Let the grid have n rows and m columns.
Time: O(n * m). The initial scan visits each cell once. Each cell is labeled and enqueued at most once, and processing a cell looks at four neighbours.
Space: O(n * m). In the worst case, such as a grid that is mostly zeros, the queue holds a large share of the cells. The distances overwrite the grid, so no second matrix is needed.
Edge cases and common mistakes
- All zeros. Nothing is marked
-1, so the search changes nothing and the grid comes back as it was. - A single zero.
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 0]]becomes[[5, 4, 3, 2], [4, 3, 2, 1], [3, 2, 1, 0]], the distance growing away from the corner. - A single row or column.
[[1, 0, 1, 1, 1]]becomes[[1, 0, 1, 2, 3]]. - Zeros in opposite corners.
[[0, 1, 1], [1, 1, 1], [1, 1, 0]]becomes[[0, 1, 2], [1, 2, 1], [2, 1, 0]]. Each cell takes the smaller of its two possible distances because the nearer zero's wave arrives first. - Using a stack instead of a queue. Taking from the back of the array makes the search depth-first, and cells could be labeled through long detours.
- Forgetting to mark the 1s with
-1. Without the marker, the check for unvisited cells fails, and cells with value 1 would be mistaken for distances. - No zeros at all. The statement guarantees at least one. With none, every cell would stay
-1.
Testing
[[0,0,0],[0,1,0],[0,0,0]]gives[[0,0,0],[0,1,0],[0,0,0]].[[0,0,0],[0,1,0],[1,1,1]]gives[[0,0,0],[0,1,0],[1,2,1]].[[0],[1],[1],[1]]gives[[0],[1],[2],[3]].[[1,0,1,1,1]]gives[[1,0,1,2,3]].[[0]]gives[[0]].