LeetCode Entry

934. Shortest Bridge

21.05.2023 medium 2023 kotlin

Find the shortest path from one island of 1's to another.

934. Shortest Bridge medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/219

Problem TLDR

Find the shortest path from one island of 1’s to another.

Intuition

Shortest path can be found with Breadth-First Search if we start it from every border cell of the one of the islands. To detect border cell, we have to make separate DFS.

Approach

• modify grid to store visited set

  Complexity

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

Code

fun Array<IntArray>.inRange(xy: Pair<Int, Int>) = (0..lastIndex).let {
    xy.first in it && xy.second in it
}
fun Pair<Int, Int>.siblings() = arrayOf(
(first - 1) to second, first to (second - 1),
(first + 1) to second, first to (second + 1)
)
fun shortestBridge(grid: Array<IntArray>): Int {
    val queue = ArrayDeque<Pair<Int, Int>>()
    fun dfs(x: Int, y: Int) {
        if (grid[y][x] == 1) {
            grid[y][x] = 2
            (x to y).siblings().filter { grid.inRange(it) }.forEach { dfs(it.first, it.second) }
        } else if (grid[y][x] == 0) queue.add(x to y)
    }
    (0 until grid.size * grid.size)
    .map { it / grid.size to it % grid.size}
    .filter { (y, x) -> grid[y][x] == 1 }
    .first().let { (y, x) -> dfs(x, y)}
    return with (queue) {
        var steps = 1
        while (isNotEmpty()) {
            repeat(size) {
                val xy = poll()
                if (grid.inRange(xy)) {
                    val (x, y) = xy
                    if (grid[y][x] == 1) return@shortestBridge steps - 1
                    if (grid[y][x] == 0) {
                        grid[y][x] = 3
                        addAll(xy.siblings().filter { grid.inRange(it) })
                    }
                }
            }
            steps++
        }
        -1
    }
}