Last updated on July 21st, 2024 at 04:27 am
Here, We see Trapping Rain Water II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Breadth-First Search, Heap
Companies
Google, Twitter
Level of Question
Hard
Trapping Rain Water II LeetCode Solution
Table of Contents
Problem Statement
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
1. Trapping Rain Water II Solution C++
class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int vol = 0;
const int M = heightMap.size(), N = heightMap[0].size();
vector<vector<bool>> visited(M, vector<bool>(N, false));
vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
auto comp = [&](const array<int, 3>& a, const array<int, 3>& b) { return a[0] >= b[0]; };
priority_queue<array<int, 3>, vector<array<int, 3>>, decltype(comp)> min_heap(comp);
for(int i = 0; i < N; i++) {
min_heap.push({heightMap[0][i], 0, i}),
min_heap.push({heightMap[M-1][i], M-1, i});
visited[0][i] = true, visited[M-1][i] = true;
}
for(int i = 0; i < M; i++) {
min_heap.push({heightMap[i][0], i, 0}),
min_heap.push({heightMap[i][N-1], i, N-1});
visited[i][0] = true, visited[i][N-1] = true;
}
while(!min_heap.empty()) {
auto [height, row, col] = min_heap.top();
min_heap.pop();
for(auto dir: directions) {
int r = row + dir[0], c = col + dir[1];
if(r >= 0 && r < M && c >= 0 && c < N && !visited[r][c]) {
visited[r][c] = true;
if(heightMap[r][c] < height)
vol += height - heightMap[r][c];
min_heap.push({max(height, heightMap[r][c]), r, c});
}
}
}
return vol;
}
};
2. Trapping Rain Water II Solution Java
public class Solution {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
List<int[]>[] g;
int start;
private int[] dijkstra() {
int[] dist = new int[g.length];
Arrays.fill(dist, Integer.MAX_VALUE / 2);
dist[start] = 0;
TreeSet<int[]> tree = new TreeSet<>((u, v) -> u[1] == v[1] ? u[0] - v[0] : u[1] - v[1]);
tree.add(new int[]{start, 0});
while (!tree.isEmpty()) {
int u = tree.first()[0], d = tree.pollFirst()[1];
for (int[] e : g[u]) {
int v = e[0], w = e[1];
if (Math.max(d, w) < dist[v]) {
tree.remove(new int[]{v, dist[v]});
dist[v] = Math.max(d, w);
tree.add(new int[]{v, dist[v]});
}
}
}
return dist;
}
public int trapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) return 0;
int r = heightMap.length, c = heightMap[0].length;
start = r * c;
g = new List[r * c + 1];
for (int i = 0; i < g.length; i++) g[i] = new ArrayList<>();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (i == 0 || i == r - 1 || j == 0 || j == c - 1) g[start].add(new int[]{i * c + j, 0});
for (int k = 0; k < 4; k++) {
int x = i + dx[k], y = j + dy[k];
if (x >= 0 && x < r && y >= 0 && y < c) g[i * c + j].add(new int[]{x * c + y, heightMap[i][j]});
}
}
int ans = 0;
int[] dist = dijkstra();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
int cb = dist[i * c + j];
if (cb > heightMap[i][j]) ans += cb - heightMap[i][j];
}
return ans;
}
}
3. Trapping Rain Water II Solution JavaScript
var trapRainWater = function (heightMap) {
if (heightMap.length < 3) return 0;
if (heightMap[0].length < 3) return 0;
let arr = new Array(heightMap.length);
let pq = new PQ();
let total = 0;
for (let i = 0; i < arr.length; i++) {
arr[i] = new Array(heightMap[i].length).fill(false);
}
for (let i = 0; i < heightMap.length; i++) {
for (let j = 0; j < heightMap[i].length; j++) {
if (i === 0 || i === heightMap.length - 1) {
pq.push([i, j, heightMap[i][j]]);
} else if (j === 0 || j === arr[i].length - 1) {
pq.push([i, j, heightMap[i][j]]);
}
}
}
while (!pq.isEmpty()) {
let [i, j, height] = pq.pop();
arr[i][j] = true;
const dir = [[0, 1], [0, -1], [-1, 0], [1, 0]];
for (let [nI, nJ] of dir) {
if ((i + nI) >= heightMap.length) continue;
if ((i + nI) < 0) continue;
if ((j + nJ) >= heightMap[i].length) continue;
if ((j + nJ) < 0) continue;
if (arr[i + nI][j + nJ]) continue;
if (heightMap[i + nI][j + nJ] < height) {
total += (height - heightMap[i + nI][j + nJ]);
heightMap[i + nI][j + nJ] = height;
}
arr[i + nI][j + nJ] = true;
pq.push([i + nI, j + nJ, heightMap[i + nI][j + nJ]])
}
}
return total;
};
class PQ {
constructor() {
this.heap = [];
}
push(element) {
this.heap.push(element);
this.bubbleUp(this.heap.length - 1);
}
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.sinkDown(0);
}
return top;
}
peek() {
return this.heap[0];
}
isEmpty() {
return this.heap.length === 0;
}
bubbleUp(index) {
let element = this.heap[index];
while (index > 0) {
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (element[2] >= parent[2]) break;
this.heap[parentIndex] = element;
this.heap[index] = parent;
index = parentIndex;
}
}
sinkDown(index) {
let length = this.heap.length;
let element = this.heap[index];
let elementPriority = element[2];
while (true) {
let smallestChildIndex = null;
let smallestChildPriority = Infinity;
let leftChildIndex = 2 * index + 1;
let rightChildIndex = 2 * index + 2;
if (leftChildIndex < length) {
let leftChild = this.heap[leftChildIndex];
let leftChildPriority = leftChild[2];
if (leftChildPriority < smallestChildPriority) {
smallestChildIndex = leftChildIndex;
smallestChildPriority = leftChildPriority;
}
}
if (rightChildIndex < length) {
let rightChild = this.heap[rightChildIndex];
let rightChildPriority = rightChild[2];
if (rightChildPriority < smallestChildPriority) {
smallestChildIndex = rightChildIndex;
smallestChildPriority = rightChildPriority;
}
}
if (smallestChildIndex === null || elementPriority < smallestChildPriority) break;
this.heap[index] = this.heap[smallestChildIndex];
this.heap[smallestChildIndex] = element;
index = smallestChildIndex;
}
}
}
4. Trapping Rain Water II Solution Python
class Solution(object):
def trapRainWater(self, heightMap):
m = len(heightMap)
n = len(heightMap[0])
heights = {}
heap = []
for r in range(m):
for c in range(n):
if r == 0 or r == m - 1 or c == 0 or c == n - 1:
h = heightMap[r][c]
heights[(r, c)] = h
heapq.heappush(heap, (h, (r, c)))
total = 0
while len(heap) > 0:
_, (r, c) = heapq.heappop(heap)
for r_o, c_o in [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]:
if 0 <= r_o < m and 0 <= c_o < n and (r_o, c_o) not in heights:
h = max(heights[(r, c)], heightMap[r_o][c_o])
heights[(r_o, c_o)] = h
total += h - heightMap[r_o][c_o]
heapq.heappush(heap, (h, (r_o, c_o)))
return total