LeetCode 407 – Trapping Rain Water II solved with a Dijkstra‑style Priority Queue

The article first remarks on how many large companies now enforce strict academic degree requirements in recruitment, often filtering out candidates whose first degree is not from a top university, which can affect even experienced engineers.

It then presents the LeetCode problem 407 “Trapping Rain Water II”, which asks to compute how much water can be trapped on a 2‑D height map.

After showing example inputs and outputs, the solution is explained as a variant of Dijkstra’s algorithm combined with a min‑heap (priority queue). The outer boundary cells are treated as the initial frontier, and the algorithm expands inward, always processing the cell with the lowest current height to determine the water that can be stored at each position.

The key insight is that the water level at a cell is limited by the minimum of the maximum heights along any path to the boundary; using a priority queue guarantees that when a cell is popped, its height is final, analogous to Dijkstra’s correctness.

Implementation details include initializing the heap with all border cells, maintaining a visited matrix, and updating neighboring cells’ heights and accumulated water.

class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue
q = new PriorityQueue<>((a,b)->a[2]-b[2]);
        boolean[][] vis = new boolean[m][n];
        for (int i = 0; i < n; i++) {
            q.add(new int[]{0, i, heightMap[0][i]});
            q.add(new int[]{m - 1, i, heightMap[m - 1][i]});
            vis[0][i] = vis[m - 1][i] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            q.add(new int[]{i, 0, heightMap[i][0]});
            q.add(new int[]{i, n - 1, heightMap[i][n - 1]});
            vis[i][0] = vis[i][n - 1] = true;
        }
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        int ans = 0;
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int x = poll[0], y = poll[1], h = poll[2];
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny]) continue;
                if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
                q.add(new int[]{nx, ny, Math.max(heightMap[nx][ny], h)});
                vis[nx][ny] = true;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int trapRainWater(vector
>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        auto cmp = [](const vector
& a, const vector
& b) { return a[2] > b[2]; };
        priority_queue
, vector
>, decltype(cmp)> q(cmp);
        vector
> vis(m, vector
(n, false));
        for (int i = 0; i < n; i++) {
            q.push({0, i, heightMap[0][i]});
            q.push({m - 1, i, heightMap[m - 1][i]});
            vis[0][i] = vis[m - 1][i] = true;
        }
        for (int i = 1; i < m - 1; i++) {
            q.push({i, 0, heightMap[i][0]});
            q.push({i, n - 1, heightMap[i][n - 1]});
            vis[i][0] = vis[i][n - 1] = true;
        }
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        int ans = 0;
        while (!q.empty()) {
            auto cell = q.top(); q.pop();
            int x = cell[0], y = cell[1], h = cell[2];
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || vis[nx][ny]) continue;
                if (h > heightMap[nx][ny]) ans += h - heightMap[nx][ny];
                q.push({nx, ny, max(h, heightMap[nx][ny])});
                vis[nx][ny] = true;
            }
        }
        return ans;
    }
};

The time complexity is O(m·n·log(m·n)) because each cell is inserted and removed from the heap at most once, and the space complexity is O(m·n) for the visited array and the heap.