Trapping rain water ii

Array Breadth-First Search Heap (Priority Queue) Matrix

64.0% acceptance

Jan 13, 2026

4996

171

Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn trap_rain_water(height_map: Vec<Vec<i32>>) -> i32 {
    if height_map.is_empty() || height_map[0].is_empty() {
      return 0;
    }
    
    let m = height_map.len();
    let n = height_map[0].len();
    let mut visited = vec![vec![false; n]; m];
    let mut heap = BinaryHeap::new();
    
    for i in 0..m {
      heap.push(Reverse((height_map[i][0], i, 0)));
      heap.push(Reverse((height_map[i][n - 1], i, n - 1)));
      visited[i][0] = true;
      visited[i][n - 1] = true;
    }
    
    for j in 1..n - 1 {
      heap.push(Reverse((height_map[0][j], 0, j)));
      heap.push(Reverse((height_map[m - 1][j], m - 1, j)));
      visited[0][j] = true;
      visited[m - 1][j] = true;
    }
    
    let mut water = 0;
    let dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)];
    
    while let Some(Reverse((h, x, y))) = heap.pop() {
      for (dx, dy) in dirs.iter() {
        let nx = x as i32 + dx;
        let ny = y as i32 + dy;
        
        if nx >= 0 && nx < m as i32 && ny >= 0 && ny < n as i32 {
          let nx = nx as usize;
          let ny = ny as usize;
          if !visited[nx][ny] {
            visited[nx][ny] = true;
            water += h.max(height_map[nx][ny]) - height_map[nx][ny];
            heap.push(Reverse((h.max(height_map[nx][ny]), nx, ny)));
          }
        }
      }
    }
    
    water
  }
}