0542 01 Matrix

Solved at: 2023-01-30

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

swift

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    }}

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.

Question

Solution

Results

Complexity Analysis

Other Answers Online