Solution with explanation and visualization | BFS + MinHeap (Beats 87.5~100 in Time and Space)
IntuitionThe problem requires calculating the amount of water that can be trapped on a 2D elevation map after rainfall.
The primary intuition here is to leverag
# Intuition
The problem requires calculating the amount of water that can be trapped on a 2D elevation map after rainfall.  
The primary intuition here is to leverage the concept of water filling the lowest elevation first, constrained by surrounding boundaries.  
To achieve this, we can utilize a **min-heap** to always process the lowest elevation boundary, ensuring that the trapped water is calculated correctly. The process simulates how water spreads from low-lying areas outward until the boundaries are filled.

# Approach
1. **Min-Heap**: Use a min-heap to track the lowest height boundary during the simulation. This allows efficient retrieval of the current lowest height for processing.
2. **Boundary Initialization**: Add all boundary cells to the min-heap since water can only escape through the edges. Mark these cells as visited to avoid reprocessing.
3. **Dijkstra-Like Expansion**: Process the cells in the min-heap:
   - Remove the smallest height cell.
   - For each unvisited neighbor of the current cell:
     - If the neighbor's height is lower than the current height, calculate the trapped water as the difference between the two heights.
     - Update the neighbor's height to the current height (simulating filling it with water).
     - Push the neighbor into the min-heap for further processing.

This approach ensures that water is always filled level by level, starting from the lowest boundary.

## Why update the neighbor's height?
- **Simulating water filling**: The neighbor's height is updated to represent the new water level.
- **Prevent incorrect reprocessing**: Without updating, the algorithm might double-count trapped water in the same area.
- **Maintain correct boundaries**: Updating the height ensures that the simulation always respects the current water level, controlled by the min-heap.

### Example
**Input**:
```typescript
const heightMap = [
  [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1]
];
```

**Boundary Heights**:
- The boundary heights are:

| - | 0     | 1     | 2     | 3     | 4     | 5     |
|---|-------|-------|-------|-------|-------|-------|
| 0 | **1** | **4** | **3** | **1** | **3** | **2** |
| 1 | **3** |       |       |       |       | **4** |
| 2 | **2** | **3** | **3** | **2** | **3** | **1** |

- These heights are added to the min-heap and marked as visited.

**Processing**:
1. Process the smallest height in the heap and calculate the trapped water for its neighbors.
2. For each neighbor:
   - If its height is lower, calculate the trapped water and update its height to the current height.
   - Add the neighbor to the heap for further processing.

**Final Result**:
- After processing all cells, the total trapped water is **4**.

**Visualize**

Test Case 1
![TestCase1.gif](https://assets.leetcode.com/users/images/23b4e70b-698f-4d7c-bc90-07daaf2e3d4b_1737289758.6050024.gif)


Test Case 2
![TestCase2.gif](https://assets.leetcode.com/users/images/a1d877b4-ffab-45ce-95e7-3d1ae0fb0176_1737289767.2333136.gif)


You can play it on GitPage in [Code Playground](https://whats2000.github.io/DailyLeetCode/407-Trapping%20Rain%20Water%20II/heap-visualization/index.html)

# Complexity
- Time Complexity:
    **Initialization**:
    - Adding all boundary cells to the heap takes $O(m + n)$.
    
    **Heap Operations**:
    - Each cell is added and removed from the heap once, and heap operations take $O(\log(m \times n))$.
    - Total complexity: $O(m \times n \log(m \times n))$.

- Space Complexity:
    - The heap requires $O(m \times n)$ space in the worst case.
    - The `visited` array also uses $O(m \times n)$ space.

### Code
```typescript
/**
 * A basic MinHeap implementation for the problem
 */
class MinHeap<T> {
  /**
   * The heap array where elements are stored
   * @private
   */
  private readonly heap: T[];
  /**
   * The comparator function used to order the elements in the heap
   * @private
   */
  private readonly comparator: (a: T, b: T) => number;

  /**
   * Creates a new MinHeap
   * @param comparator The comparator function used to order the elements in the heap
   */
  constructor(comparator: (a: T, b: T) => number) {
    this.heap = [];
    this.comparator = comparator;
  }

  /**
   * Pushes a new value into the heap
   * @param value The value to push
   */
  push(value: T): void {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  /**
   * Pops the smallest value from the heap
   * @returns The smallest value in the heap
   */
  pop(): T | undefined {
    if (this.size() === 0) return undefined;
    if (this.size() === 1) return this.heap.pop();
    const root = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.heapifyDown(0);
    return root;
  }

  /**
   * Returns the smallest value in the heap
   * @returns The smallest value in
    */
  peek(): T | undefined {
    return this.heap[0];
  }

  /**
   * Returns the size of the heap
   * @returns The size of the heap
   */
  size(): number {
    return this.heap.length;
  }

  /**
   * Restores the heap property by moving the element up
   * @param index The index of the element to move up
   * @private
   */
  private heapifyUp(index: number): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.comparator(this.heap[index], this.heap[parentIndex]) >= 0) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  /**
   * Restores the heap property by moving the element down
   * @param index The index of the element to move down
   * @private
   */
  private heapifyDown(index: number): void {
    const size = this.size();
    while (index < size) {
      let smallest = index;
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;

      if (leftChild < size && this.comparator(this.heap[leftChild], this.heap[smallest]) < 0) {
        smallest = leftChild;
      }
      if (rightChild < size && this.comparator(this.heap[rightChild], this.heap[smallest]) < 0) {
        smallest = rightChild;
      }
      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

const MOVE_DIRECTIONS = [
  { dx: 0, dy: 1 },
  { dx: 1, dy: 0 },
  { dx: 0, dy: -1 },
  { dx: -1, dy: 0 },
];

function trapRainWater(heightMap: number[][]): number {
  // Get the dimensions of the matrix
  const m = heightMap.length;    // number of rows
  const n = heightMap[0].length; // number of columns

  // Edge case: If the matrix is too small, it can't trap water
  // Because the water requires at least 3 x 3 cells to be trapped
  if (m < 3 || n < 3) return 0;

  // Initialize the visited array and the min heap
  const visited = Array.from({ length: m }, () => Array(n).fill(false));
  const minHeap = new MinHeap<{ height: number; row: number; col: number }>(
    (a, b) => a.height - b.height
  );

  // Add all boundary cells to the heap
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      //  If the cell is not a boundary cell, skip it
      if (i !== 0 && i !== m - 1 && j !== 0 && j !== n - 1) {
        continue;
      }

      // Push the boundary cell into the heap
      minHeap.push({ height: heightMap[i][j], row: i, col: j });

      // Mark the cell as visited
      visited[i][j] = true;
    }
  }
  let trappedWater = 0;

  // Process cells in the heap
  while (minHeap.size() > 0) {
    const { height, row, col } = minHeap.pop()!;

    // Check the neighbors of the current cell
    for (const { dx, dy } of MOVE_DIRECTIONS) {
      const newRow = row + dx;
      const newCol = col + dy;

      // Check if the neighbor is within bounds and not visited
      if (
        newRow < 0 ||
        newRow >= m ||
        newCol < 0 ||
        newCol >= n ||
        visited[newRow][newCol]
      ) {
        continue;
      }

      // Mark the neighbor as visited
      visited[newRow][newCol] = true;

      // Calculate the trapped water
      // The trapped water is the difference between the height of the current cell and the height of the neighbor cell
      trappedWater += Math.max(0, height - heightMap[newRow][newCol]);

      // Push the neighbor cell into the heap
      minHeap.push({
        height: Math.max(height, heightMap[newRow][newCol]),
        row: newRow,
        col: newCol,
      });
    }
  }

  return trappedWater;
}
```

# Result
![image.png](https://assets.leetcode.com/users/images/3d143aad-0871-41c9-826d-a81731e73085_1737289823.6647549.png)

['Array', 'Breadth-First Search', 'Heap (Priority Queue)', 'TypeScript']