Problem overview
The method computeGrid receives grid, a matrix of 0s and 1s with at least one 0. It returns a matrix of the same shape in which each cell holds the distance to the nearest 0. Cells move one step at a time: up, down, left or right, and each step costs 1. Diagonal moves are not allowed.
For [[0,0,0],[0,1,0],[1,1,1]] the answer is [[0,0,0],[0,1,0],[1,2,1]]. Every 0 stays 0. The 1 in the middle is next to a 0, so its distance is 1. The bottom-middle cell needs 2 steps: up to the middle cell, then up to the 0 above it. The bottom corners are next to the 0 in the middle row, so they get 1.
Approach: start the search from every zero at once
The direct idea runs a search from every 1 until it finds a 0. That repeats a lot of work: with many cells, each search can cover the whole matrix, and the total grows with the square of the number of cells.
Flip the question. Instead of asking each 1 for its nearest 0, let every 0 spread outward together. This is a multi-source breadth-first search (BFS). Put all the zeros in the queue first, each at distance 0. Then process the queue: a cell removed from the front gives each unvisited neighbour a distance one larger than its own, and the neighbour joins the back of the queue.
The queue holds cells in order of distance, so a cell is first reached from its nearest zero, and that first label is its final answer. Each cell enters the queue at most once, so the work is proportional to the size of the matrix.
The grid itself keeps the state. Before the search, every 1 is replaced by -1, meaning "not reached yet". Distances are never negative, so a cell holding -1 is exactly an unvisited one. At the end, the same grid holds the answer.
Step by step
- Create the queue
que, an empty array of[Int]pairs, each holding a row and a column. - Store the dimensions.
nis the number of rows,grid.count, andmthe number of columns,grid[0].count, so later bounds checks stay short. - Loop over the rows with
iin0..<n. - Loop over the columns with
jin0..<m. - Enqueue every zero. If
grid[i][j]is 0, append[i, j]. Its distance is already 0. - Mark every other cell as unvisited by setting it to
-1. - Define the four moves in a constant
directions: up, down, left and right. - Loop while the queue isn't empty.
- Take the front cell with
removeFirstand read its row and column asx1andy1. - Loop over the four moves, with
das the current offset. - Compute the neighbour as
x2andy2by addingd[0]andd[1]. - Check that it's inside the grid and still unvisited, that is, equal to
-1. The bounds tests come first. - Label it with the current cell's distance plus one.
- Enqueue it, so its own neighbours are processed later.
- Return
grid, which now holds the distances.
The solution in Swift
class Solution {
func computeGrid(_ grid: [[Int]]) -> [[Int]] {
var grid = grid
var que = [[Int]]()
let n = grid.count, m = grid[0].count
for i in 0..<n {
for j in 0..<m {
if grid[i][j] == 0 {
que.append([i, j])
} else {
grid[i][j] = -1
}
}
}
let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
while !que.isEmpty {
let front = que.removeFirst()
let x1 = front[0]
let y1 = front[1]
for d in directions {
let x2 = x1 + d[0]
let 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.append([x2, y2])
}
}
}
return grid
}
}
The Swift details worth a closer look:
- The parameter copy. Parameters are constants, so
var grid = gridmakes a mutable local copy. Arrays are value types, so the caller's matrix is not changed. - An array as a queue. Swift has no built-in queue type.
appendadds at the back andremoveFirst()removes from the front, but it shifts every remaining element, so it costsO(n)on a long array. For a matrix of up to 10,000 cells that is acceptable. A larger input would call for an integer head index that moves forward instead. - Pairs as arrays. The queue holds
[Int]pairs, read back asfront[0]andfront[1]. A tuple type would also work. - Short-circuit checks. In the neighbour test, the four bounds comparisons come before
grid[x2][y2]. Swift stops at the first false operand, so an invalid index is never read. Reading outside an array stops the program. - Several constants in one statement.
let n = grid.count, m = grid[0].countdeclares two constants at once.
Complexity
Let the matrix have R rows and C columns, so N = R * C cells.
Time: O(N) for the search. The first pass visits every cell once. In the search, each cell enters the queue at most once and checks four neighbours. With the array-based queue, removeFirst adds a cost that grows with the queue length, so the worst case is higher, but it stays small for the stated sizes.
Space: O(N). The copy of the grid takes N cells, and the queue holds at most N pairs.
Edge cases and common mistakes
- All zeros. Every cell is a source, and the answer equals the input.
- One zero in a corner.
[[0,1,1,1,1]]returns[[0,1,2,3,4]], and[[1,1,1],[1,1,1],[1,1,0]]returns[[4,3,2],[3,2,1],[2,1,0]]. - A single cell.
[[0]]returns[[0]]. - No zero at all. The lesson promises at least one. Without it, nothing enters the queue and every cell would come back as
-1. - Searching from each 1. It gives correct answers but repeats work, and it is much slower on large inputs.
- Using a stack instead of a queue. A cell might be labelled from a far zero first, and the labels would be too large.
- Using 0 as the "unvisited" marker. Zeros are real sources, so the marker has to be a value no distance can take. That is why it is
-1. - Checking bounds after the read. Reading
grid[x2][y2]before the bounds tests crashes on border cells.
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]].[[1,1,1],[1,1,1],[1,1,0]]gives[[4,3,2],[3,2,1],[2,1,0]].[[0]]gives[[0]].
