LeetCode Entry

1091. Shortest Path in Binary Matrix

01.06.2023 medium 2023 kotlin

0 path length in a binary square matrix.

1091. Shortest Path in Binary Matrix medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/232

Problem TLDR

0 path length in a binary square matrix.

Intuition

Just do BFS.

Approach

Some tricks for cleaner code:

• check for x, y in range
• iterate over dirs. This is a sequence of x and y
• modify the input array. But don’t do this in production code.

  Complexity

• Time complexity: \(O(n)\)
• Space complexity: \(O(n)\)

Code

fun shortestPathBinaryMatrix(grid: Array<IntArray>): Int =
    with(ArrayDeque<Pair<Int, Int>>()) {
        val range = 0..grid.lastIndex
        val dirs = arrayOf(0, 1, 0, -1, -1, 1, 1, -1)
        if (grid[0][0] == 0) add(0 to 0)
        grid[0][0] = -1
        var step = 0
        while (isNotEmpty()) {
            step++
            repeat(size) {
                val (x, y) = poll()
                if (x == grid.lastIndex && y == grid.lastIndex) return step
                var dx = -1
                for (dy in dirs) {
                    val nx = x + dx
                    val ny = y + dy
                    if (nx in range && ny in range && grid[ny][nx] == 0) {
                        grid[ny][nx] = -1
                        add(nx to ny)
                    }
                    dx = dy
                }
            }
        }
        -1
    }