Leetcode: As Far From Land as Possible

1162. As Far from Land as Possible

This is a classic BFS problem. Put all the land cells in the queue and run Breadth First Search to find farthest water cell or vice versa.

import java.util.*

class Solution {
    fun maxDistance(grid: Array<IntArray>): Int {
        val n = grid.size
        val ones = grid.mapIndexed { i, row ->
            row.mapIndexed { j, item ->
                if (item == 1) Pair(i, j) else null
            }.filterNotNull()
        }.flatten()
        if (ones.isEmpty() || ones.size == n * n)
            return -1
        val queue = LinkedList<Pair<Int, Int>>(ones)
        val dist = Array(n) { IntArray(n) { Int.MAX_VALUE } }
        ones.forEach { dist[it.first][it.second] = 0 }

        while (queue.isNotEmpty()) {
            val u = queue.pop()!!
            for (dir in listOf(Pair(0, 1), Pair(0, -1), Pair(1, 0), Pair(-1, 0))) {
                val v = Pair(u.first + dir.first, u.second + dir.second)
                if (!(v.first in 0 until n && v.second in 0 until n))
                    continue
                if (dist[v.first][v.second] > dist[u.first][u.second] + 1) {
                    dist[v.first][v.second] = dist[u.first][u.second] + 1
                    queue.add(v)
                }
            }
        }
        return dist.map { row ->
            row.filter { it < Int.MAX_VALUE }.max()!!
        }.max()!!
    }
}

Related Posts