# 0542 01 Matrix

Solved at: 2023-01-30

01 Matrix - LeetCode

## Question​

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

## Solution​

class Solution {
func updateMatrix(_ matrix: Int) -> Int {
// fill the zeros first

var mat = matrix
var queue: [(Int, Int)] = []

for (i, row) in mat.enumerated() {
for (j, col) in row.enumerated() {
if mat[i][j] == 0 {
queue.append((i, j))
}
mat[i][j] = -1
}
}

var level = 0

while !queue.isEmpty {
let count = queue.count
for i in 0..<count {
let (r, c) = queue.remove(at: 0)
if mat[r][c] == -1 {
mat[r][c] = level
}
if r > 0 && mat[r-1][c] == -1 {
queue.append((r-1, c))
}
if c > 0 && mat[r][c-1] == -1 {
queue.append((r, c-1))
}
if r < mat.count - 1 && mat[r+1][c] == -1 {
queue.append((r+1, c))
}
if c < mat[0].count - 1 && mat[r][c+1] == -1 {
queue.append((r, c+1))
}
}
level += 1
}
return mat
}
}

## Results​

• Time taken: 11 m 43 s
• Runtime 1856 ms, Beats 10.39%
• Memory 15.5 MB, Beats 83.12%

## Complexity Analysis​

• Time: $O(N \times c)$
• Space: $O(N \times c)$

Where $c$ is the cost — the number of iterations in which "BFS clear" operation will run.

## Other Answers Online​

Dynamic Programming in 2 passes. An easier solution will be 4 passes from left → right, right → left, top → bottom, bottom → top.