Problem overview
The input is a rectangular int[,] containing only 0s and 1s, with at least one 0. ComputeGrid must return a grid of the same shape in which each cell holds its distance to the nearest 0. Distance counts steps between cells that touch horizontally or vertically, so each step costs 1.
For the grid with rows 000 / 010 / 111, the answer has rows 000 / 010 / 121. Every 0 maps to 0. The 1 in the middle is next to a 0, so it gets 1. The bottom row's corners are each next to a 0 in the row above. The bottom middle cell is not next to any 0, so it needs two steps.
Approach: start from all the zeros at once
The obvious plan is to run a search from every 1 to find the closest 0. That repeats a lot of work: on a grid with n * m cells it can cost up to the square of the cell count. The efficient idea reverses the direction. Start from the zeros and spread outwards.
A breadth-first search (BFS) expands in layers. If you put every 0 in the queue before the search begins, then the first layer reached is all cells at distance 1 from some 0, the next layer is distance 2, and so on. The first time a cell is reached, it is reached from its nearest 0. This is a multi-source BFS: one search with many starting points.
The grid itself can store the progress. Before the search, every 1 is overwritten with -1, meaning "not reached yet". Real distances are never negative, so the marker is unambiguous. When the search labels a cell, it replaces the -1 with the distance. The check == -1 then also serves as the "not visited" test, and no second matrix is needed.
Step by step
- Create a
Queue<int[]>namedque. Each entry is a two-element array{row, column}. - Read the grid's dimensions once:
n = grid.GetLength(0)rows andm = grid.GetLength(1)columns. - Loop over every row
i, with a loop over every columnjinside it. - If the cell holds 0, enqueue its position. Zeros are already at distance 0, so they are the sources.
- Otherwise set the cell to
-1, to mark it as unvisited. - Define
directions, the four offsets for up, down, left and right. Diagonals are not neighbours. - Loop while
que.Count > 0. - Dequeue the front position and copy its coordinates into
x1andy1. Taking from the front processes the closest cells first. - Loop over
directionsand compute the neighbour(x2, y2). - Check that the neighbour is inside the grid and still holds
-1. The bounds tests come first, so the cell is only read when the indices are valid. - Set the neighbour to
grid[x1, y1] + 1. It was reached from a cell one step closer to a zero. - Enqueue the neighbour so its own neighbours are handled later.
- Return
grid, which now holds the answer.
The solution in C#
class Solution {
public int[,] ComputeGrid(int[,] grid) {
Queue<int[]> que = new Queue<int[]>();
int n = grid.GetLength(0), m = grid.GetLength(1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i, j] == 0) {
que.Enqueue(new int[]{i, j});
} else {
grid[i, j] = -1;
}
}
}
int[][] directions = new int[][] {
new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}
};
while (que.Count > 0) {
int[] front = que.Dequeue();
int x1 = front[0];
int y1 = front[1];
foreach (int[] d in directions) {
int x2 = x1 + d[0];
int y2 = y1 + d[1];
if (0 <= x2 && x2 < n && 0 <= y2 && y2 < m && grid[x2, y2] == -1) {
grid[x2, y2] = grid[x1, y1] + 1;
que.Enqueue(new int[]{x2, y2});
}
}
}
return grid;
}
}
Trace 000 / 010 / 111. The queue starts with the five zeros, in scan order, and the three 1s are now -1. Dequeuing (0, 1) labels (1, 1) with 1. Dequeuing (1, 0) labels (2, 0) with 1, and dequeuing (1, 2) labels (2, 2) with 1. The cell (2, 1) is not next to any zero, so it stays -1 until (1, 1) comes off the queue. It then gets 1 + 1 = 2.
Some C# details:
int[,]is a rectangular array. A cell isgrid[i, j], andGetLength(0)andGetLength(1)give the row and column counts.grid.Lengthis the total number of cells, which would be the wrong bound in a loop.- The input is changed. The method writes into
gridand returns the same object. The returned array and the argument are the same array. If you need the original, copy it first. - Chained comparison. C# doesn't allow
0 <= x2 < n. Each bound is its own comparison, joined by&&. - No tuple unpacking from arrays. The code reads
front[0]andfront[1]into two locals. You could also enqueue(int, int)tuples in aQueue<(int, int)>, which avoids allocating an array per cell.
Complexity
Time: O(n * m). The initial scan visits each cell once. In the search, each cell is enqueued at most once, because labelling it removes the -1, and each dequeued cell checks four neighbours.
Space: O(n * m) for the queue in the worst case (a grid that is mostly zeros puts almost every cell in it). Apart from the queue, the algorithm reuses the input grid.
Edge cases and common mistakes
- All zeros. Every cell is a source and the search finds no
-1, so the grid is returned unchanged. - A single row or column. For
{{0,1,1,1,1}}the answer is{{0,1,2,3,4}}. The bounds checks reject the neighbours above and below. - Zero far from a corner. With a single 0 in a corner of a 3 by 3 grid, the opposite corner gets distance 4, the Manhattan distance. Moving only in four directions makes the distance the sum of the row and column differences.
- Starting from the ones. Searching from each 1 to find a 0 works but is much slower on large grids.
- Not marking the ones. If the 1s are not changed to
-1, the check can't tell labelled cells from unlabelled ones, and cells would be enqueued repeatedly. - Using a stack. A stack turns the search into depth-first order, and labels would no longer be shortest distances.
Testing
- Rows
000 / 010 / 000give000 / 010 / 000. - Rows
000 / 010 / 111give000 / 010 / 121. - One row
01111gives01234. - Rows
111 / 111 / 110give432 / 321 / 210.