LeetCode Entry

778. Swim in Rising Water

06.10.2025 hard 2025 kotlin rust

Min time to swim to end, flooding every second

778. Swim in Rising Water hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1134

Problem TLDR

Min time to swim to end, flooding every second #hard #bfs

Intuition

Iterate over time (0..50^2) and do BFS step while less than time. Or, just put time variable in a PriorityQueue.

Approach

• another way is the BinarySearch: check reachability in O(n^2), do log(n) search in time
• the simple 0-1 BFS didn’t work here: all times should be sorted

Complexity

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

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

Code

// 42ms
    fun swimInWater(g: Array<IntArray>): Int {
        val q = PriorityQueue<IntArray>(compareBy { it[0] })
        var r = g[0][0]; q += intArrayOf(r,0,0); g[0][0] = -1
        while (q.size > 0) {
            val (t,y,x) = q.poll(); r = max(r,t); if (y==g.size-1&&x==g[0].size-1) break
            for ((u,r) in listOf(0,1,0,-1,0).zipWithNext())
                if (x+r in g[0].indices && y+u in g.indices && g[y+u][x+r]>=0)
                    { q += intArrayOf(g[y+u][x+r],y+u,x+r); g[y+u][x+r] = -1 }
        }; return r
    }

// 0ms
    pub fn swim_in_water(mut g: Vec<Vec<i32>>) -> i32 {
        let (n,m,mut h) = (g.len(),g[0].len(), BinaryHeap::from([(-g[0][0],0,0)]));
        g[0][0] = -1; let mut r = 0;
        while let Some((t,y,x)) = h.pop() {
            r = r.max(-t); if (y,x) == (n-1,m-1) { break }
            for (u,r) in [(y-1,x),(y+1,x),(y,x-1),(y,x+1)] {
                if u < n && r < m && g[u][r] >= 0 { h.push((-g[u][r],u,r)); g[u][r] = -1 }
        }} r
    }