# 19.01.2025 [407. Trapping Rain Water II]

Trap the water in 2D height matrix #hard #bfs

19.01.2025

407. Trapping Rain Water II hard blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/869

Problem TLDR

Trap the water in 2D height matrix #hard #bfs

Intuition

I didn't solve this myself in 2 hours.

My naive approach was the brute-force (not accepted, but correct): go layer by layer increasing height, and calculate area with BFS less than current height, track min height difference.

The optimal solution: go from outside with BFS and add height difference, append to the Heap adjacents making them at least current height. Imagine water filling everything at the level of the current min.

Approach

• spending 2 hours on a wrong idea is ok

Complexity

• Time complexity: $$O(nm)$$

• Space complexity: $$O(nm)$$

Code

    fun trapRainWater(heightMap: Array<IntArray>): Int {
        val m = heightMap.size - 1; val n = heightMap[0].size - 1; var res = 0
        val q = PriorityQueue<List<Int>>(compareBy { it[0] })
        for (y in 0..m) for (x in 0..n) if (min(x, y) < 1 || y == m || x == n)
            q += listOf(heightMap[y][x], y, x)
        while (q.size > 0) {
            val (min, y, x) = q.poll(); heightMap[y][x] = -1
            for ((y1, x1) in listOf(y to x - 1, y - 1 to x, y to x + 1, y + 1 to x))     
                if (y1 in 0..m && x1 in 0..n && heightMap[y1][x1] >= 0) {
                    q += listOf(max(min, heightMap[y1][x1]), y1, x1)
                    res += max(0, min - heightMap[y1][x1]); heightMap[y1][x1] = -1
                }
        }
        return res
    }

    pub fn trap_rain_water(mut height_map: Vec<Vec<i32>>) -> i32 {
        let (m, n, mut r) = (height_map.len(), height_map[0].len(), 0);
        let mut q = BinaryHeap::new();
        for y in 0..m { for x in 0..n { if (y.min(x) < 1 || y == m - 1 || x == n - 1) {
            q.push((-height_map[y][x], y, x)) }}}
        while let Some((min, y, x)) = q.pop() {
            height_map[y][x] = -1; let min = -min;
            for (y1, x1) in [(y, x - 1), (y - 1, x), (y, x + 1), (y + 1, x)] {
                if (0..m).contains(&y1) && (0..n).contains(&x1) && height_map[y1][x1] >= 0 {
                    q.push((-min.max(height_map[y1][x1]), y1, x1));
                    r += 0.max(min - height_map[y1][x1]); height_map[y1][x1] = -1
                }}
        }; r
    }

    int trapRainWater(vector<vector<int>>& g) {
        priority_queue<array<int,3>, vector<array<int,3>>, greater<>> q; 
        int m = size(g), n = size(g[0]), r = 0, d[] = {0, 1, 0, -1, 0};
        for (int i = 0; i < m * n; ++i) if (i < n || i >= n * (m - 1) || i % n < 1 || i % n == n - 1)
            q.push({g[i / n][i % n], i / n, i % n });
        while (size(q)) {
            auto [v, y, x] = q.top(); q.pop(); g[y][x] = -1;
            for (int i = 0; i < 4; ++i) 
                if (int y1 = y + d[i], x1 = x + d[i + 1]; min(y1, x1) >= 0 && y1 < m && x1 < n && g[y1][x1] >= 0)
                    q.push({max(v, g[y1][x1]), y1, x1}), r += max(0, v - g[y1][x1]), g[y1][x1] = -1;
        } return r;
    }