Problem overview
The method computeGrid receives a matrix of 0s and 1s as a [][]int and returns a matrix of the same size where each cell holds the distance to the nearest 0. Distance counts steps between adjacent cells, moving up, down, left or right, and each step costs 1. The matrix contains at least one 0.
In the second example, [[0,0,0],[0,1,0],[1,1,1]], every 0 is at distance 0. The 1 in the middle touches a 0, so its distance is 1. The bottom-left and bottom-right 1s are also next to a 0. The bottom-middle 1 has no 0 directly beside it, so its nearest 0 is two steps away, and the answer is [[0,0,0],[0,1,0],[1,2,1]].
Approach: start the search from all zeros at once
The direct idea is to search outward from every 1 until a 0 turns up. That repeats a lot of work, and the cost can reach the square of the number of cells.
The better idea runs the search backwards. Instead of asking each 1 "where is your nearest 0?", start from the zeros and spread outward. A breadth-first search (BFS) explores in layers of equal distance, so if every zero starts in the queue together, the first time the search reaches a cell is along a shortest path from the nearest zero. That is a multi-source BFS. The cells next to a zero get 1, the cells next to those get 2, and so on.
The grid itself can store the progress. Before the search, every 1 is replaced by -1, which means "no distance yet". Real distances are never negative, so -1 can't be confused with one. A neighbor is processed only while it is still -1, which makes each cell enter the queue at most once.
Step by step
- Declare a small
pairstruct with fieldsxandyinside the method, and an empty slicequeof pairs as the BFS queue. A type declared in a function is visible only there. - Store the sizes as
n, m := len(grid), len(grid[0])so the bounds checks stay short. - Loop over every cell with
iandj. - Enqueue every zero. Append
pair{i, j}toque. Their distance is already 0. - Mark every other cell as
-1, in theelsebranch. - Create
directionswith the four offsets: up, down, left and right. - Loop while
queis not empty. - Pop the front: copy
que[0]intofront, reslice withque = que[1:], and read its coordinates asx1andy1. - Range over
directions, and compute the neighborx2,y2by adding the offsets. - Check the neighbor. It must be inside the grid and still
-1. - Label it with the current cell's distance plus 1 and append it to the queue.
- Return
grid, which now holds the distances.
The solution in Go
type Solution struct{}
func (this Solution) computeGrid(grid [][]int) [][]int {
type pair struct{ x, y int }
que := []pair{}
n, m := len(grid), len(grid[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 0 {
que = append(que, pair{i, j})
} else {
grid[i][j] = -1
}
}
}
directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
for len(que) > 0 {
front := que[0]
que = que[1:]
x1, y1 := front.x, front.y
for _, d := range directions {
x2 := x1 + d[0]
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 = append(que, pair{x2, y2})
}
}
}
return grid
}
The Go details worth knowing:
- A struct for a coordinate pair.
type pair struct{ x, y int }declares a local type, andpair{i, j}builds a value by field order. Named fields read better than a two-element slice. - A slice works as a queue.
appendadds at the back andque = que[1:]drops the front without copying any element. elsemust follow the closing brace on the same line. The layout} else {is required by the language, and a newline beforeelseis a syntax error.- No chained comparisons. A bounds test is written as separate comparisons joined by
&&. Because&&short-circuits,grid[x2][y2]is read only after the coordinates pass the range checks. Putting that read first would panic on an edge cell. - The input is changed and returned. The function writes into
gridand returns that same slice, so the caller's matrix holds the answer afterwards. If the original must stay intact, copy it first. - Blank identifier.
for _, d := range directionsignores the index, because Go rejects unused variables.
Complexity
The setup loop visits each of the n * m cells once. In the BFS every cell is enqueued at most once, since it stops being -1 the moment it is labeled, and each dequeue examines four neighbors. The time is O(n * m). The queue can hold up to O(n * m) cells, for example when the matrix is all zeros, so the extra space is O(n * m). The distances reuse the input matrix and need no separate one.
Edge cases and common mistakes
- A single zero.
[[0]]returns[[0]]. The queue starts with one cell and its neighbors are all out of range. - A single row.
[[1,1,1,0]]returns[[3 2 1 0]]. - Far from the zero.
[[1,1,1],[1,1,1],[1,1,0]]gives[[4 3 2] [3 2 1] [2 1 0]], so the farthest cell is 4 steps away. - No zero at all. The note guarantees at least one, because with none the queue starts empty and every cell would stay
-1. - Not marking the 1s. If they stay 1, the check "still unvisited" has nothing to test, and cells would be revisited.
- Using the back of the queue. Taking cells from the end makes the search depth-first, and the labels would no longer be the shortest distances.
- Labeling when dequeuing instead of enqueuing. The same cell could then be queued several times by different neighbors.
Testing
[[0,0,0],[0,1,0],[0,0,0]]returns[[0 0 0] [0 1 0] [0 0 0]].[[0,0,0],[0,1,0],[1,1,1]]returns[[0 0 0] [0 1 0] [1 2 1]].[[1,1,1,0]]returns[[3 2 1 0]].