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.