LeetCode Entry

1970. Last Day Where You Can Still Cross

30.06.2023 hard 2023 kotlin

Last day matrix connected top-bottom when flooded each day at cells[day]

1970. Last Day Where You Can Still Cross hard blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/261

Problem TLDR

Last day matrix connected top-bottom when flooded each day at cells[day]

Intuition

One possible solution is to do a Binary Search in a days space, however it gives TLE. Let’s invert the problem: find the first day from the end where there is a connection top-bottom. image.png Now, cells[day] is a new ground. We can use Union-Find to connect ground cells.

Approach

  • use sentinel cells for top and bottom
  • use path compressing uf[n] = x

Complexity

  • Time complexity: \(O(an)\), where a is a reverse Ackerman function

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

Code


val uf = HashMap<Int, Int>()
fun root(x: Int): Int = if (uf[x] == null || uf[x] == x) x else root(uf[x]!!)
.also { uf[x] = it }
fun latestDayToCross(row: Int, col: Int, cells: Array<IntArray>) =
    cells.size - 1 - cells.reversed().indexOfFirst { (y, x) ->
        uf[y * col + x] = root(if (y == 1) 0 else if (y == row) 1 else y * col + x)
        sequenceOf(y to x - 1, y to x + 1, y - 1 to x, y + 1 to x)
        .filter { (y, x) -> y in 1..row && x in 1..col }
        .map { (y, x) -> y * col + x }
        .forEach { if (uf[it] != null) uf[root(y * col + x)] = root(it) }
        root(0) == root(1)
    }