Trapping Rain Water II
Trapping Rain Water II is a hard heaps problem solved with the advanced pattern.
The best approach, optimal (min-heap flood from the border), runs in O(m · n · log(m · n)) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (relax water levels until stable) up.
Problem
You are given an m x n grid heightMap where each cell holds the height of a block of ground. Rain falls on the whole area and fills every dip it can. Water spreads between cells that share a side, and anything that reaches the border of the grid flows away.
Return the total amount of water, in unit cubes, that stays trapped on the grid after the rain.
Examples
Example 1
- Input
heightMap = [[5, 5, 5, 5], [5, 1, 2, 5], [5, 5, 5, 5]]- Output
7- Why
- Both inner cells are enclosed by walls of height 5, so they fill up to 5: (5 - 1) + (5 - 2) = 7.
Example 2
- Input
heightMap = [[4, 4, 4, 4, 4], [4, 0, 3, 0, 2], [4, 4, 4, 4, 4]]- Output
5- Why
- The right wall dips to 2, so the cell next to it fills only to 2. The 3 in the middle shields the left cell, which fills to 3. Total 3 + 0 + 2 = 5.
Example 3
- Input
heightMap = [[2, 2, 2], [2, 7, 2], [2, 2, 2]]- Output
0- Why
- The only inner cell is higher than everything around it, so no water stays.
Constraints
m == heightMap.length,n == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (relax water levels until stable) | O((m · n)²) | O(m · n) |
| Optimal (min-heap flood from the border) | O(m · n · log(m · n)) | O(m · n) |
1Brute force (relax water levels until stable)
O((m · n)²)A pass costs O(m · n) and each pass fixes at least one more cell, so in the worst case there are O(m · n) passes.O(m · n)One level per cell.Give each border cell a water level equal to its height and every inner cell an infinite level. The true level of an inner cell is max(its height, smallest level among its four neighbours). Apply that rule to every inner cell over and over until nothing changes; the levels then equal the true water surface, and the answer is the sum of level minus height.
- level[i][j] = height for border cells, infinity for inner cells.
- Repeat: for every inner cell, set level = max(height, min of the 4 neighbour levels); remember whether anything changed.
- Stop after a full pass with no change.
- Return the sum of level[i][j] - height[i][j] over all cells.
class Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
int[][] level = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean border = i == 0 || j == 0 || i == m - 1 || j == n - 1;
level[i][j] = border ? heightMap[i][j] : Integer.MAX_VALUE;
}
}
boolean changed = true;
while (changed) {
changed = false;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
int low = Math.min(Math.min(level[i - 1][j], level[i + 1][j]),
Math.min(level[i][j - 1], level[i][j + 1]));
int next = Math.max(heightMap[i][j], low);
if (next < level[i][j]) {
level[i][j] = next;
changed = true;
}
}
}
}
int water = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) water += level[i][j] - heightMap[i][j];
}
return water;
}
}class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
INF = float("inf")
level = [[heightMap[i][j] if i in (0, m - 1) or j in (0, n - 1) else INF
for j in range(n)] for i in range(m)]
changed = True
while changed:
changed = False
for i in range(1, m - 1):
for j in range(1, n - 1):
low = min(level[i - 1][j], level[i + 1][j], level[i][j - 1], level[i][j + 1])
nxt = max(heightMap[i][j], low)
if nxt < level[i][j]:
level[i][j] = nxt
changed = True
return sum(level[i][j] - heightMap[i][j] for i in range(m) for j in range(n))class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size(), n = heightMap[0].size();
vector<vector<int>> level(m, vector<int>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
bool border = i == 0 || j == 0 || i == m - 1 || j == n - 1;
level[i][j] = border ? heightMap[i][j] : INT_MAX;
}
}
bool changed = true;
while (changed) {
changed = false;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
int low = min(min(level[i - 1][j], level[i + 1][j]), min(level[i][j - 1], level[i][j + 1]));
int next = max(heightMap[i][j], low);
if (next < level[i][j]) {
level[i][j] = next;
changed = true;
}
}
}
}
int water = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) water += level[i][j] - heightMap[i][j];
}
return water;
}
};function trapRainWater(heightMap) {
const m = heightMap.length, n = heightMap[0].length;
const level = [];
for (let i = 0; i < m; i++) {
level.push([]);
for (let j = 0; j < n; j++) {
const border = i === 0 || j === 0 || i === m - 1 || j === n - 1;
level[i].push(border ? heightMap[i][j] : Infinity);
}
}
let changed = true;
while (changed) {
changed = false;
for (let i = 1; i < m - 1; i++) {
for (let j = 1; j < n - 1; j++) {
const low = Math.min(level[i - 1][j], level[i + 1][j], level[i][j - 1], level[i][j + 1]);
const next = Math.max(heightMap[i][j], low);
if (next < level[i][j]) {
level[i][j] = next;
changed = true;
}
}
}
}
let water = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) water += level[i][j] - heightMap[i][j];
}
return water;
}2Optimal (min-heap flood from the border)
O(m · n · log(m · n))Each cell is pushed and popped once, and each heap operation costs O(log(m · n)).O(m · n)The visited grid and the heap can each hold every cell.Treat the border as the wall of a pool and always work from its lowest point, because that is where water would escape first. Start with all border cells in a min-heap keyed by their level (their height). Pop the lowest cell: any unvisited neighbour can be filled up to that level, since every way out from it passes a wall at least that high. The neighbour then becomes part of the wall with level max(level, its height). This is Dijkstra's algorithm where the path cost is the highest wall on the path.
- Push every border cell into a min-heap as (height, row, col) and mark it visited.
- Pop the cell with the lowest level.
- For each unvisited neighbour: mark it visited, add max(0, level - its height) to the answer, and push it with level max(level, its height).
- Repeat until the heap is empty and return the total.
class Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
boolean[][] seen = new boolean[m][n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
pq.offer(new int[] { heightMap[i][j], i, j });
seen[i][j] = true;
}
}
}
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int water = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
for (int[] d : dirs) {
int r = cur[1] + d[0], c = cur[2] + d[1];
if (r < 0 || c < 0 || r >= m || c >= n || seen[r][c]) continue;
seen[r][c] = true;
water += Math.max(0, cur[0] - heightMap[r][c]);
pq.offer(new int[] { Math.max(cur[0], heightMap[r][c]), r, c });
}
}
return water;
}
}import heapq
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
seen = [[False] * n for _ in range(m)]
heap = []
for i in range(m):
for j in range(n):
if i == 0 or j == 0 or i == m - 1 or j == n - 1:
heap.append((heightMap[i][j], i, j))
seen[i][j] = True
heapq.heapify(heap)
water = 0
while heap:
level, i, j = heapq.heappop(heap)
for r, c in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= r < m and 0 <= c < n and not seen[r][c]:
seen[r][c] = True
water += max(0, level - heightMap[r][c])
heapq.heappush(heap, (max(level, heightMap[r][c]), r, c))
return waterclass Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size(), n = heightMap[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
pq.push({heightMap[i][j], i, j});
seen[i][j] = true;
}
}
}
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
int water = 0;
while (!pq.empty()) {
array<int, 3> cur = pq.top();
pq.pop();
for (int k = 0; k < 4; k++) {
int r = cur[1] + dr[k], c = cur[2] + dc[k];
if (r < 0 || c < 0 || r >= m || c >= n || seen[r][c]) continue;
seen[r][c] = true;
water += max(0, cur[0] - heightMap[r][c]);
pq.push({max(cur[0], heightMap[r][c]), r, c});
}
}
return water;
}
};function trapRainWater(heightMap) {
const m = heightMap.length, n = heightMap[0].length;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
// binary min-heap of [level, row, col]
const heap = [];
const push = (item) => {
heap.push(item);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p][0] <= heap[i][0]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let s = i;
if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
if (s === i) break;
[heap[s], heap[i]] = [heap[i], heap[s]];
i = s;
}
}
return top;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
push([heightMap[i][j], i, j]);
seen[i][j] = true;
}
}
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let water = 0;
while (heap.length > 0) {
const [level, i, j] = pop();
for (const [dr, dc] of dirs) {
const r = i + dr, c = j + dc;
if (r < 0 || c < 0 || r >= m || c >= n || seen[r][c]) continue;
seen[r][c] = true;
water += Math.max(0, level - heightMap[r][c]);
push([Math.max(level, heightMap[r][c]), r, c]);
}
}
return water;
}Edge cases to test
- One row or one column: every cell is on the border and nothing can be held
- A gap in the outer wall lowers the water level of everything behind it
- Inner walls split the grid into basins with different water levels
- Water level of a cell is limited by the lowest point on its best escape route, not by its direct neighbours alone
Hints
Hint 1
Water above a cell can rise only until it finds a way out to the border. The final level of a cell is the lowest possible 'highest wall' over all paths from the cell to the outside.
Hint 2
The border cells hold no water. Think of the border as the outside wall, and push inward from its lowest point first, because that is where water would spill out.
Hint 3
Put every border cell in a min-heap by height. Pop the lowest cell; each unvisited neighbour can hold max(0, level - its height), and its own level becomes max(level, its height). Push it and repeat.
FAQ
What is the best time complexity for Trapping Rain Water II?
Optimal (min-heap flood from the border) runs in O(m · n · log(m · n)) time and O(m · n) extra space. Each cell is pushed and popped once, and each heap operation costs O(log(m · n)).
Which pattern does Trapping Rain Water II use?
It is a heaps problem that uses the advanced pattern. Other problems with the same pattern: Find K Pairs with Smallest Sums, Find Median from Data Stream, Minimum Number of Refueling Stops.
Is there a brute force solution for Trapping Rain Water II?
Yes. Brute force (relax water levels until stable) takes O((m · n)²) time and O(m · n) space. Give each border cell a water level equal to its height and every inner cell an infinite level.
Which edge cases should I test for Trapping Rain Water II?
One row or one column: every cell is on the border and nothing can be held; A gap in the outer wall lowers the water level of everything behind it; Inner walls split the grid into basins with different water levels; Water level of a cell is limited by the lowest point on its best escape route, not by its direct neighbours alone.