LeetCode in Kotlin

542. 01 Matrix

Medium

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.

Example 1:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]

Output: [[0,0,0],[0,1,0],[0,0,0]]

Example 2:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]

Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Solution

class Solution {
    fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
        val dist = Array(mat.size) { IntArray(mat[0].size) }
        for (i in mat.indices) {
            dist[i].fill(Int.MAX_VALUE - 100000)
        }
        for (i in mat.indices) {
            for (j in mat[0].indices) {
                if (mat[i][j] == 0) {
                    dist[i][j] = 0
                } else {
                    if (i > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1)
                    }
                    if (j > 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1)
                    }
                }
            }
        }
        for (i in mat.indices.reversed()) {
            for (j in mat[0].indices.reversed()) {
                if (i < mat.size - 1) {
                    dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1)
                }
                if (j < mat[0].size - 1) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1)
                }
            }
        }
        return dist
    }
}

This site is open source. Improve this page.