LeetCode Entry

542. 01 Matrix

17.08.2023 medium 2023 kotlin

Distances to 0 in an 0-1 matrix

542. 01 Matrix medium blog post substack image.png

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 code
  • avoid 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
    }