Problem overview
The method computeGrid receives a grid of 0s and 1s as an Array[Array[Int]]. 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. The method returns a grid of the same shape holding those distances. The grid has at least one 0 and at most 10,000 cells.
In the second example the input is [[0,0,0],[0,1,0],[1,1,1]] and the output is [[0,0,0],[0,1,0],[1,2,1]]. Every 0 has distance 0. The 1 in the middle touches a 0, so its distance is 1. The bottom-left and bottom-right cells also touch a 0 from above, so they are 1. The bottom-middle cell needs two steps: its upper neighbor is a 1, but that neighbor touches a 0.
Approach: start the search from every zero at once
The direct way is to run a search from each 1 until it meets a 0. That repeats a lot of work. The key idea is to reverse the search: start from all the zeros together and spread outward one step at a time.
This is a multi-source breadth-first search. Put every 0 into a queue, each already at distance 0. Then repeatedly take a cell from the front, look at its four neighbors, and give every neighbor that has no distance yet a distance one larger than the current cell's. Cells leave the queue in order of increasing distance, so the first time a cell is reached comes from its nearest 0, which makes that distance final.
The grid itself serves as the bookkeeping. Before the search, every 1 is overwritten with -1 to mean "not reached yet". Real distances are never negative, so the marker can't be confused with an answer. After the search, no -1 is left in any cell that can be reached from a zero.
Step by step
- Create the queue, an empty
mutable.Queue[Array[Int]]namedque. Each entry is a(row, column)pair stored as a two-element array. - Store the dimensions.
nisgrid.length(rows) andmisgrid(0).length(columns). - Loop over the rows with
iin0 until n. - Loop over the columns with
jin0 until m. - Enqueue every zero. If
grid(i)(j)is 0, addArray(i, j)to the queue. These are the sources, already at distance 0. - Mark every other cell with
-1, meaning "not visited". - Create
directions, an array of the four offsets for up, down, left and right. Diagonal cells aren't neighbors. - Loop while the queue is not empty.
- Take the front pair with
dequeue()and unpack it intox1andy1. - Loop over
directions, naming each offsetd, withd(0)for the row andd(1)for the column. - Compute the neighbor
(x2, y2)by adding the offsets. - Check it is inside the grid and unvisited. The bounds tests come first, and
&&skips the rest when one fails, sogrid(x2)(y2)is only read for cells that exist. The last test isgrid(x2)(y2) == -1. - Label the neighbor with
grid(x1)(y1) + 1. - Enqueue it, so its own neighbors are examined later.
- End with
gridas the last expression.
The solution in Scala
class Solution {
def computeGrid(grid: Array[Array[Int]]): Array[Array[Int]] = {
val que = mutable.Queue[Array[Int]]()
val n = grid.length
val m = grid(0).length
for (i <- 0 until n) {
for (j <- 0 until m) {
if (grid(i)(j) == 0) {
que.enqueue(Array(i, j))
} else {
grid(i)(j) = -1
}
}
}
val directions = Array(Array(-1, 0), Array(1, 0), Array(0, -1), Array(0, 1))
while (que.nonEmpty) {
val front = que.dequeue()
val x1 = front(0)
val y1 = front(1)
for (d <- directions) {
val x2 = x1 + d(0)
val y2 = y1 + d(1)
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && grid(x2)(y2) == -1) {
grid(x2)(y2) = grid(x1)(y1) + 1
que.enqueue(Array(x2, y2))
}
}
}
grid
}
}
The Scala details worth a closer look:
- The
mutableprefix.mutable.Queuecomes fromscala.collection.mutable, so a standalone file needsimport scala.collection.mutable. Scala's default collections are immutable, and a queue you can add to in place is the mutable one. - Two sets of parentheses.
grid(i)(j)reads rowi, then columnj. Assignment looks the same:grid(i)(j) = -1. - The input is changed in place. An
Arrayis mutable, and the method returns the same array it was given. Afterval r = computeGrid(g),randgrefer to one object. Copy the grid first to keep the original. Array(i, j)builds a two-elementArray[Int]used as a pair. The compiler doesn't know it has exactly two elements, so the code relies on always creating it with two.- Last expression. The method ends with
grid, so noreturnis needed.
Complexity
Let the grid have n rows and m columns.
Time: O(n * m). The setup scan visits each cell once. In the search, every cell is enqueued at most once, because labeling it removes the -1 that allowed it in, and each dequeued cell examines four neighbors.
Space: O(n * m). The queue can hold every cell in the worst case, for example when the grid is all zeros. The distances are written into the input grid, so no second matrix is needed.
Edge cases and common mistakes
- All zeros.
[[0,0,0],[0,0,0]]comes back unchanged. - A single row.
[[0,1,1,1,1]]becomes[[0,1,2,3,4]]. - A single column.
[[0],[1],[1],[1]]becomes[[0],[1],[2],[3]]. - No zero at all. The statement guarantees one. Without a zero the queue starts empty, and a grid such as
[[1,1],[1,1]]comes back filled with-1. - Marking cells after dequeuing. A cell could then be enqueued by several neighbors, repeating work. The method labels a cell when it enqueues it.
- Leaving the 1s in place. Without the
-1marker, the code can't tell an unvisited cell from a 1 that has already been given the value 1 as a real distance. - A stack instead of a queue. The distances would no longer be the shortest ones.
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,1]]gives[[0,1,2,3,4]].[[0],[1],[1],[1]]gives[[0],[1],[2],[3]].
