The O(n) Club: Trapping Rain Water II: How to Flood a 2D Matrix Without Crying

The O(n) Club: Trapping Rain Water II — How to Flood a 2D Matrix Without Crying

⚡ TL;DR

This is the classic LeetCode problem where you desperately try to keep water inside a grid, but the water (like your bugs) always looks for low ground. Brute force means simulating every possible dam like a stubborn civil engineer. Or, you could just use a min-heap and let the water fill itself. Java snippet for those allergic to TMI:

// Brute force: For your "learning only" nightmares
int water = 0;
for (int i = 1; i < m - 1; i++) {
  for (int j = 1; j < n - 1; j++) {
    int minBound = Math.min(
      maxInRowLeft(i, j),
      maxInRowRight(i, j),
      maxInColUp(i, j),
      maxInColDown(i, j)
    );
    water += Math.max(0, minBound - heightMap[i][j]);
  }
}

🧠 How Devs Usually Mess This Up

The go-to move: “Hey, I’ll just do my usual 1D two-pointer dance on every row and column!” Sorry, but water in 2D is as uncontainable as a sleep-deprived developer’s sarcasm. Two pointers don’t work. If you use a max-heap, the water will laugh at you and escape. You have to process from the lowest boundary cell (use a min-heap), and—news flash—edges can’t hold water, so anything less than 3 rows or columns is an exercise in futility.

🔍 What’s Actually Going On

This whole ordeal is like trying to fill a wobbly salad bowl: the moment you pour more water, it seeks out the lowest rim. In the grid, that’s your boundary. Real rainwater fills depressions from the edge inward, so the only sane way is to process lowest walls first. As you pop cells from the heap, you try to fill the little valleys formed by their neighbors. Sometimes you succeed. Sometimes you just invent a new leak.

🛠️ PseudoCode

• If grid is smaller than 3×3, return 0. (Seriously, don’t waste CPU cycles.)
• Shove all boundary cells into a min-heap and mark them as “visited.” (Water can’t stay there anyway.)
• While the heap isn’t empty:
  • Pop the cell with lowest height.
  • For each of its 4 boring non-diagonal neighbors:
    • If it’s NOT visited:
    • Mark neighbor as visited (one time only, no standing ovations).
    • Calculate water as max(0, currentCell.height – neighbor.height).
    • Add any water you just conjured to the total.
    • Offer the neighbor to the heap with height = max(currentCell.height, neighbor.height).

Repeat until you drown the grid (metaphorically, please).

💻 The Code

import java.util.*;
 class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        if (m < 3 || n < 3) return 0;
        boolean[][] visited = new boolean[m][n];
        PriorityQueue
<cell> heap = new PriorityQueue<>(Comparator.comparingInt(c -> c.height));
         // Add all boundary cells
        for (int i = 0; i < m; i++) {
            heap.offer(new Cell(i, 0, heightMap[i][0]));
            heap.offer(new Cell(i, n - 1, heightMap[i][n - 1]));
            visited[i][0] = visited[i][n - 1] = true;
        }
        for (int j = 1; j < n - 1; j++) {
            heap.offer(new Cell(0, j, heightMap[0][j]));
            heap.offer(new Cell(m - 1, j, heightMap[m - 1][j]));
            visited[0][j] = visited[m - 1][j] = true;
        }
         int water = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!heap.isEmpty()) {
            Cell cell = heap.poll();
            for (int[] d : dirs) {
                int ni = cell.i + d[0], nj = cell.j + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
                    visited[ni][nj] = true;
                    water += Math.max(0, cell.height - heightMap[ni][nj]);
                    heap.offer(new Cell(ni, nj, Math.max(heightMap[ni][nj], cell.height)));
                }
            }
        }
        return water;
    }
     static class Cell {
        int i, j, height;
        Cell(int i, int j, int h) {
            this.i = i; this.j = j; this.height = h;
        }
    }
}
</cell>

⚠️ Pitfalls, Traps & Runtime Smacks

• Edges do nothing: Boundaries are just there for show—no water trapped.
• Teeny Tiny Grids: Got less than 3 rows or 3 columns? Save your cycles. Return 0.
• Wrong Heap = Wrong Results: Min-heap only. Max-heap is a ticket to test case purgatory.
• Double Dips: If you don’t mark visited, enjoy your infinite water and even more infinite bugs.
• Why so slow? O(mn log(mn)) because every cell is a special snowflake in your heap.
• Space hog: Yes, it’s O(mn) for both heap and visited grid. Sorry, Raspberry Pi.

🧠 Interviewer Brain-Tattoo

Always fill from the outside in, just like coffee stains on your favorite shirt. And never trust the boundaries — they’re just there for dramatic effect.