407. Trapping Rain Water II LeetCode Solution

In this guide, you will get 407. Trapping Rain Water II LeetCode Solution with the best time and space complexity. The solution to Trapping Rain Water II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Trapping Rain Water II solution in C++
Trapping Rain Water II solution in Java
Trapping Rain Water II solution in Python
Additional Resources

407. Trapping Rain Water II LeetCode Solution image

Problem Statement of Trapping Rain Water II

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.

Example 1:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.

Example 2:

Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10

Constraints:

m == heightMap.length
n == heightMap[i].length
1 <= m, n <= 200
0 <= heightMap[i][j] <= 2 * 104

Complexity Analysis

Time Complexity: O(mn\log mn)
Space Complexity: O(mn)

407. Trapping Rain Water II LeetCode Solution in C++

struct T {
  int i;
  int j;
  int h;  // heightMap[i][j] or the height after filling water
};

class Solution {
 public:
  int trapRainWater(vector<vector<int>>& heightMap) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = heightMap.size();
    const int n = heightMap[0].size();
    int ans = 0;
    auto compare = [](const T& a, const T& b) { return a.h > b.h; };
    priority_queue<T, vector<T>, decltype(compare)> minHeap(compare);
    vector<vector<bool>> seen(m, vector<bool>(n));

    for (int i = 0; i < m; ++i) {
      minHeap.emplace(i, 0, heightMap[i][0]);
      minHeap.emplace(i, n - 1, heightMap[i][n - 1]);
      seen[i][0] = true;
      seen[i][n - 1] = true;
    }

    for (int j = 1; j < n - 1; ++j) {
      minHeap.emplace(0, j, heightMap[0][j]);
      minHeap.emplace(m - 1, j, heightMap[m - 1][j]);
      seen[0][j] = true;
      seen[m - 1][j] = true;
    }

    while (!minHeap.empty()) {
      const auto [i, j, h] = minHeap.top();
      minHeap.pop();
      for (const auto& [dx, dy] : dirs) {
        const int x = i + dx;
        const int y = j + dy;
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        if (heightMap[x][y] < h) {
          ans += h - heightMap[x][y];
          minHeap.emplace(x, y, h);  // Fill water in grid[x][y].
        } else {
          minHeap.emplace(x, y, heightMap[x][y]);
        }
        seen[x][y] = true;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

407. Trapping Rain Water II LeetCode Solution in Java

class T {
  public int i;
  public int j;
  public int h; // heightMap[i][j] or the height after filling water
  public T(int i, int j, int h) {
    this.i = i;
    this.j = j;
    this.h = h;
  }
}

class Solution {
  public int trapRainWater(int[][] heightMap) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = heightMap.length;
    final int n = heightMap[0].length;
    int ans = 0;
    Queue<T> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.h, b.h));
    boolean[][] seen = new boolean[m][n];

    for (int i = 0; i < m; ++i) {
      minHeap.offer(new T(i, 0, heightMap[i][0]));
      minHeap.offer(new T(i, n - 1, heightMap[i][n - 1]));
      seen[i][0] = true;
      seen[i][n - 1] = true;
    }

    for (int j = 1; j < n - 1; ++j) {
      minHeap.offer(new T(0, j, heightMap[0][j]));
      minHeap.offer(new T(m - 1, j, heightMap[m - 1][j]));
      seen[0][j] = true;
      seen[m - 1][j] = true;
    }

    while (!minHeap.isEmpty()) {
      final int i = minHeap.peek().i;
      final int j = minHeap.peek().j;
      final int h = minHeap.poll().h;
      for (int[] dir : dirs) {
        final int x = i + dir[0];
        final int y = j + dir[1];
        if (x < 0 || x == m || y < 0 || y == n)
          continue;
        if (seen[x][y])
          continue;
        if (heightMap[x][y] < h) {
          ans += h - heightMap[x][y];
          minHeap.offer(new T(x, y, h)); // Fill water in grid[x][y].
        } else {
          minHeap.offer(new T(x, y, heightMap[x][y]));
        }
        seen[x][y] = true;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

407. Trapping Rain Water II LeetCode Solution in Python

class Solution:
  def trapRainWater(self, heightMap: list[list[int]]) -> int:
    dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
    m = len(heightMap)
    n = len(heightMap[0])
    ans = 0
    minHeap = []
    seen = set()

    for i in range(m):
      heapq.heappush(minHeap, (heightMap[i][0], i, 0))
      heapq.heappush(minHeap, (heightMap[i][n - 1], i, n - 1))
      seen.add((i, 0))
      seen.add((i, n - 1))

    for j in range(1, n - 1):
      heapq.heappush(minHeap, (heightMap[0][j], 0, j))
      heapq.heappush(minHeap, (heightMap[m - 1][j], m - 1, j))
      seen.add((0, j))
      seen.add((m - 1, j))

    while minHeap:
      h, i, j = heapq.heappop(minHeap)
      for dx, dy in dirs:
        x = i + dx
        y = j + dy
        if x < 0 or x == m or y < 0 or y == n:
          continue
        if (x, y) in seen:
          continue
        if heightMap[x][y] < h:
          ans += h - heightMap[x][y]
          # Fill water in grid[x][y].
          heapq.heappush(minHeap, (h, x, y))
        else:
          heapq.heappush(minHeap, (heightMap[x][y], x, y))
        seen.add((x, y))

    return ans
 # code by PROGIEZ