17.08.2023
542. 01 Matrix medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/311
Problem TLDR
Distances to 0
in an 0-1
matrix
Intuition
Depth-First search will not work, as the path to 0
must radiate to all directions.
We can start a Breadth-First Search waves from each 0
. Each BFS step increases distance by 1.
Approach
use
dir
array for a simpler codeavoid rewriting the cells
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun updateMatrix(mat: Array<IntArray>): Array<IntArray> {
val res = Array(mat.size) { IntArray(mat[0].size) { -1 } }
val dir = listOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)
with(ArrayDeque<Pair<Int, Int>>()) {
for (y in 0..mat.lastIndex)
for (x in 0..mat[0].lastIndex)
if (mat[y][x] == 0) add(y to x)
var dist = 0
while (isNotEmpty()) {
repeat(size) {
val (y, x) = poll()
if (res[y][x] == -1) {
res[y][x] = dist
for ((dx, dy) in dir) {
val y1 = y + dy
val x1 = x + dx
if (y1 in 0..mat.lastIndex && x1 in 0..mat[0].lastIndex)
add(y1 to x1)
}
}
}
dist++
}
}
return res
}