Trapping Rain Water II

Hard
928.

Trapping Rain Water II

Trapping Rain Water II is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Twitter interviews.

An m × n matrix gives the height of each unit cell of a 2D elevation map. Return the volume of water it can trap after raining. Water runs off the edges of the map.

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
The four interior cells hold 4 units between them.

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
Explanation
A wall of 3 all round: eight cells fill by 1 and the centre by 2.

Example 3

Input
heightMap = [[1,1,1],[1,0,1],[1,1,1]]
Output
1

Constraints

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function(heightMap) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Trapping Rain Water II — Solution in Python, Java & C++

Trapping Rain Water II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Trapping Rain Water II is a hard coding problem on arrays, matrix and breadth-first search, asked in Amazon, Google and Twitter interviews.

Problem statement

An m × n matrix gives the height of each unit cell of a 2D elevation map. Return the volume of water it can trap after raining. Water runs off the edges of the map.

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: The four interior cells hold 4 units between them.

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
Explanation: A wall of 3 all round: eight cells fill by 1 and the centre by 2.

Example 3

Input: heightMap = [[1,1,1],[1,0,1],[1,1,1]]
Output: 1

Constraints

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 10^4

Hints for Trapping Rain Water II

  1. Hint 1

    The 1D two-pointer trick does not generalise: in 2D, water escapes through the lowest point of the surrounding rim, wherever it is.

  2. Hint 2

    Start from the border — those cells can hold nothing — and work inward from the lowest rim cell each time.

  3. Hint 3

    A min-heap keyed on the current water level gives that order.

How to solve Trapping Rain Water II

Flood inward from the boundary, always processing the lowest cell on the current rim. When the rim's lowest cell has level L, any unvisited neighbour below L is filled to L, because L is the cheapest way out of the basin.

Approach

  1. Push every border cell onto a min-heap keyed by its height, and mark it visited.
  2. Pop the lowest cell, with water level L.
  3. For each unvisited neighbour: if its height is below L, it traps L - height; push it back at level max(L, height).
  4. Continue until the heap empties.

Why it works

Processing the rim in increasing order of level is the whole argument: when a cell is popped at level L, every other route out of the region is at least L high, so L is exactly the water level at its neighbours — no later discovery can lower it. Pushing a neighbour at max(L, height) carries that boundary forward, since a taller cell raises the rim rather than letting water out.

Complexity

  • Time — O(m · n · log(m · n))
  • Space — O(m · n)

Pitfalls

  • Marking a cell visited when it is pushed — not when popped — keeps each cell out of the heap more than once.
  • A grid narrower than 3 in either direction traps nothing; it is all border.
  • The pushed level is max(level, height), not the raw height, or a basin behind a tall wall leaks.

Reference solution

Python

from typing import List
import heapq

def trapRainWater(heightMap: List[List[int]]) -> int:
    m, n = len(heightMap), len(heightMap[0])
    if m < 3 or n < 3:
        return 0
    seen = [[False] * n for _ in range(m)]
    heap = []
    for i in range(m):
        for j in range(n):
            if i not in (0, m - 1) and j not in (0, n - 1):
                continue
            seen[i][j] = True
            heapq.heappush(heap, (heightMap[i][j], i, j))
    total = 0
    while heap:
        level, r, c = heapq.heappop(heap)
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if not (0 <= nr < m and 0 <= nc < n) or seen[nr][nc]:
                continue
            seen[nr][nc] = True
            if heightMap[nr][nc] < level:
                total += level - heightMap[nr][nc]
            heapq.heappush(heap, (max(level, heightMap[nr][nc]), nr, nc))
    return total

Java

public static int trapRainWater(int[][] heightMap) {
    int m = heightMap.length, n = heightMap[0].length;
    if (m < 3 || n < 3) return 0;
    boolean[][] seen = new boolean[m][n];
    PriorityQueue<int[]> heap = 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 && i != m - 1 && j != 0 && j != n - 1) continue;
            seen[i][j] = true;
            heap.add(new int[] { heightMap[i][j], i, j });
        }
    }
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int total = 0;
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int level = cur[0], r = cur[1], c = cur[2];
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            if (heightMap[nr][nc] < level) total += level - heightMap[nr][nc];
            heap.add(new int[] { Math.max(level, heightMap[nr][nc]), nr, nc });
        }
    }
    return total;
}

C++

int trapRainWater(vector<vector<int>>& heightMap) {
    int m = (int) heightMap.size(), n = (int) heightMap[0].size();
    if (m < 3 || n < 3) return 0;
    vector<vector<char>> seen(m, vector<char>(n, 0));
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> heap;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i != 0 && i != m - 1 && j != 0 && j != n - 1) continue;
            seen[i][j] = 1;
            heap.push({ heightMap[i][j], i, j });
        }
    }
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    int total = 0;
    while (!heap.empty()) {
        auto cur = heap.top();
        heap.pop();
        int level = cur[0], r = cur[1], c = cur[2];
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = 1;
            if (heightMap[nr][nc] < level) total += level - heightMap[nr][nc];
            heap.push({ max(level, heightMap[nr][nc]), nr, nc });
        }
    }
    return total;
}

JavaScript

var trapRainWater = function(heightMap) {
    var m = heightMap.length, n = heightMap[0].length, i, j;
    if (m < 3 || n < 3) return 0;
    var seen = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(false);
        seen.push(row);
    }
    // The heap holds level * 40000 + cell, so a plain int heap is enough:
    // m * n <= 40000 and the level fits well inside 32 bits.
    var heap = [];
    var push = function(v) {
        heap.push(v);
        var k = heap.length - 1;
        while (k > 0) {
            var p = (k - 1) >> 1;
            if (heap[p] <= heap[k]) break;
            var t = heap[p]; heap[p] = heap[k]; heap[k] = t;
            k = p;
        }
    };
    var pop = function() {
        var top = heap[0];
        var last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            var k = 0;
            for (;;) {
                var l = 2 * k + 1, r = l + 1, s = k;
                if (l < heap.length && heap[l] < heap[s]) s = l;
                if (r < heap.length && heap[r] < heap[s]) s = r;
                if (s === k) break;
                var t = heap[s]; heap[s] = heap[k]; heap[k] = t;
                k = s;
            }
        }
        return top;
    };
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i !== 0 && i !== m - 1 && j !== 0 && j !== n - 1) continue;
            seen[i][j] = true;
            push(heightMap[i][j] * 40000 + i * n + j);
        }
    }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var total = 0;
    while (heap.length > 0) {
        var key = pop();
        var level = Math.floor(key / 40000);
        var cell = key % 40000;
        var cr = Math.floor(cell / n), cc = cell % n;
        for (var d = 0; d < 4; d++) {
            var nr = cr + dr[d], nc = cc + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
            seen[nr][nc] = true;
            if (heightMap[nr][nc] < level) total += level - heightMap[nr][nc];
            var next = heightMap[nr][nc] > level ? heightMap[nr][nc] : level;
            push(next * 40000 + nr * n + nc);
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal